NpCompleteness - Algoviz Wiki

Works

Yes

Description

An HTML tutorial interspersed with applets for showing various heuristics to solve the TSP problem.

Evaluation

Strengths: Very clear, very simple visualizations/ Weaknesses: Clearly a tutorial, you see what happens at a logical level, but not a lot of details for how it might be implemented.

Step Control; Random Data

Exploring the Concept; Lecture Aid

Screenshots

Videos

References

First Visited

2009-01-14

Last Visited

2009-01-14

Last Updated

1999

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://research.cs.vt.edu/AVresearch/Swan/

Edit

You may edit this entry if you have an account.

Swan - Vertex Cover

Recommendation

Has Potential

Link

Delivery Method

Windows Application

License

GPL

Language

English

Author

Jun Yang; Cliff Shaffer

Institution

Virginia Tech

Project

Swan

Works

Yes

Description

Simple demonstration allowing the user to try to pick a vertex cover.

Evaluation

Only useful for demonstrating the problem of vertex cover by allowing user to try to solve it. No algorithm for solving the problem is provided. While it is easy to use once you know what to do, the interface could be made clearer. The program must be restarted to try again.

Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-08

Last Visited

2008-06-27

Last Updated

1996

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www-cse.uta.edu/~cook/ai1/lectures/applets/gatsp/TSP.html

Edit

You may edit this entry if you have an account.

UTAtsp

Recommendation

Unrated

Link

Delivery Method

License

Language

English

Author

Diane Cook

Institution

University of Texas, Arlington

Project

Works

Unavailable

Description

Traveling salesman.

Evaluation

Screenshots

Videos

References

First Visited

Last Visited

Last Updated

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://students.ceid.upatras.gr/~papagel/project/tspprobl.htm

Edit

You may edit this entry if you have an account.

UPatras Traveling Salesperson

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Language

English

Author

Institution

University of Patras

Project

UPatras Collection

PartOfCollection

Works

Yes

Description

This example presents a greedy heuristic algorithm for Traveling Salesperson problem.

Evaluation

The example provides good, thorough and simple enough explanation on the Traveling Salesperson problem and the greedy heuristic algorithm that is used. The visualization of the algorithm shows not how the pseudo-code is executed (it is provided separately), but how the algorithm chooses the next path. Pressing only the "Solve" button is rather confusing, as it seems like the visualization is merely a "test how this algorithm works" example, but next to it is a "Step" button, which justifies the example's usefulness in learning the problem and a one heuristic solution for it. The paths' costs are also modifiable instead of just providing fixed input. This improves student engagement and gets him/her to stay with the example longer.

Teaching the Concept

Screenshots

Videos

References

First Visited

2008

Last Visited

2008-06-13

Last Updated

Topic

Community

Average rating:	4.0
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

AlViE - Hamiltonian Path

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

Works

Yes

Description

Walkthrough showing a proof that Hamiltonian Path is NP-complete.

Evaluation

Simple-to-use user interface for walking through the example. Simply open up the AV (see directions below) and step through the example with pseudo-code. As you go through the example, you are directed to the corresponding line in the pseudocode and given a line or two of explanation in the message window. Attractive layout of the data, including colors.

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/hamiltonianPathNPCompleteness.swf

Lecture Aid; Self Study

Screenshots

Videos

References

Download and unzip the ALVIE system from the website. Double click on the .jar file. Within the ALVIE pane (not the GRIND pane), click on the "eye" icon (third icon from the left in the toolbar) to get a list of algorithms from which select the AV that you want. Once selected, click OK and step through the AV with the arrow icons.

First Visited

2010-01-29

Last Visited

2010-01-29

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

AlViE - Subset Sum

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

Works

Yes

Description

Walkthrough showing a proof that the Subset Sum problem is NP-complete.

Evaluation

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/subsetSumNPCompleteness.swf

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2010-01-29

Last Visited

2010-01-29

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

AlViE - Three-Coloring

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

Works

Yes

Description

Walkthrough showing an NP-completeness proof for the Three-Coloring problem.

Evaluation

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/threeColoringNPCompleteness.swf

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2010-01-29

Last Visited

2010-01-29

Last Updated

2009-12-20

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

Edit

You may edit this entry if you have an account.

AlViE - Vertex Cover

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

Works

Yes

Description

Walkthrough showing an NP-completeness proof for the Vertex Cover problem.

Evaluation

Step Control; Canned Data

http://sites.google.com/site/alviehomepage/alvie3/downoads/vertexCoverNPCompleteness.swf

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2010-02-02

Last Visited

2010-02-02

Last Updated

2010-02-02

Topic

Community

Average rating:	unrated
Your rating:	You must be logged in to Rate.

http://www-cg-hci.informatik.uni-oldenburg.de/~da/iva/baer/binpacking/index.html

Edit

You may edit this entry if you have an account.

JCAT Binpacking

Recommendation

Unrated

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Marc Najork; Marc Brown

Institution

DEC SRI

Project

JCAT

Works

Yes

Description

Shows examples of first-fit binpacking.

Evaluation

User can watch it animate, or step through. There isn't really much to see, since it just shows first-fit, and doesn't discuss complexity or better algorithsm.

Animation; Random Data; Step Control

Lecture Aid

Screenshots

Videos

References