DynamicProgramming - Algoviz Wiki

Works

Yes

Description

Visualization for solving least common subsequence problem using dynamic programming.

Evaluation

The AV is set up as a series of "slides" in one pane, and pseudocode in the adjacent pane. As the user steps through the "slides", the associated pseudocode is highlighted. Occasional questions pop up for the user to answer. This AV has some supporting explanatory information, but it really needs some additional support such as a lecture or textbook content.

Step Control; Questions; Canned Data; User Data

Lecture Aid; Lab Exercise

Screenshots

Videos

References

Clicking on the link above will take you to a login page for Jhave. If you do not want to create an account at jhave.org, use anonymous@anonymous.com as your user name and anonymous as your password when you are asked to login. You will then be taken to the Jhave page for this AV. Some Jhave AVs include a tutorial on how the AV itself or the underlying algorithm works. At the bottom are links to the AV (you can run it with a built-in quiz system on or off). The first time you try to run any Jhave exercise, you will have to download the Jhave webstart application. This should happen automatically when you click the link. (You might need to install Java WebStart if it is not on your machine.) Once you download the Jhave application, the AV should start automatically. You can then step through the AV by repeatedly clicking the right arrow button. Occasionally, you will be given a multiple-choice or short-answer question to answer.

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

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.

JHAVÉ - Dynamic Programming - Edit Distance

Recommendation

Has Potential

Link

http://jhave.org/learner

Delivery Method

Java Web Start

License

CreativeCommons

Language

English

Author

Tom Naps

Institution

University of Wisconsin - Oshkosh

Project

JHAVÉ

Works

Yes

Description

Visualization for solving the minimum edit distance problem using dynamic programming.

Evaluation

Step Control; Questions; Canned Data; User Data

Lecture Aid; Lab Exercise

Screenshots

Videos

References

First Visited

2008-07-08

Last Visited

2008-07-10

Last Updated

2008-07-01

Topic

Community

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

http://www.cs.usfca.edu/galles/visualization/download.html

Edit

You may edit this entry if you have an account.

Data Structure Visualization - Dynamic Programming

Recommendation

Has Potential

Link

Delivery Method

Java Application

License

Unlicensed Sourcecode

Language

English

Author

David Galles

Institution

University of San Francisco

Project

Data Structure Visualization

Works

Yes

Description

Demonstrations for two different simple dynamic programming examples: Fibonacci series and making change. For each one, there are three versions: Making a full table from the bottom up; using "memoized" recursive calls where the auxiliary table avoids duplicate calls; and a naive recursive implementation without dynamic programming.

Evaluation

Helpful AV for getting started with dynamic programming, though this could be much better. There is no explanation for what is going on as the algorithm progresses. Seeing the pseudocode does help here. The change example suffers greatly from the fact that it is not at all clear what is going on -- what are the sizes of the coins? The values in the table don't really make sense. Having the three versions of the algorithm does help to illustrate why dynamic programming can be effective. It would be nice to get some sort of performance statistics, or watch them side-by-side for better comparison.

Animation; Step Control; User Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-09-01

Last Visited

2008-07-02

Last Updated

2006-04-05

Topic

Community

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

http://www.animal.ahrgr.de/showAnimationDetails.php3?anim=19

Edit

You may edit this entry if you have an account.

Animal - Knapsack

Recommendation

Has Potential

Link

Delivery Method

Animal Animation

License

Non-Commercial

Language

English

Author

Angelo Sarto; John Hastings; Karen Tuinstra; John Hensgen

Institution

TU Darmstadt, Darmstadt, Germany

Project

Animal

Works

Yes

Description

Presents a slideshow with an example walking through a dynamic programming implementation for the Knapsack problem.

Evaluation

Clear presentation, should be understandable by students. The Animal site has other Knapsack examples, some using Dynamic Programming, others using variations on Branch and Bound.

Animation; Step Control; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

For detailed instructions on how to install Animal and run Animal AVs, see: http://www.algoanim.info/Animal2/?q=node/290. Once you have installed the Animal .jar file and downloaded/unpacked the .zip file of Animal animations, you are now ready to run Animal. Run the .jar file to start Animal. Then go to the "Open" menu item, and browse to where you put the animal animations you got in the .zip file. Pick this AV from the list. You can then step through the animation, or use "kiosk mode" to have the steps fed to you at a constant pace.

First Visited

2007-07-21

Last Visited

2010-02-04

Last Updated

2000-05-17

Topic

Community

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

http://www.cs.auckland.ac.nz/software/AlgAnim/mat_chain.html#mat_chain_anim

Edit

You may edit this entry if you have an account.

Auckland - Chained Matrix Multiplication

Recommendation

Has Potential

Link

Delivery Method

Java Applet

License

Unavailable

Language

English

Author

Woi Ang; John Morris

Institution

University of Auckland

Project

Morris' Collection

PartOfCollection

Works

Yes

Description

This a visualization of chained matrix multiplication using dynamic programming to find the optimal multiplication ordering. The main page is a textual description of why finding an optimal ordering for matrix chain multiplication is important and some explanation of how it works. The visualization itself shows the assorted tables that need to be built and walks through the process of trying all of the combinations to find the lowest cost ordering. There are only four controls, 'stop', 'run, 'step', and 'skip'. The first three controls are exactly what one would expect, while the skip button jump to different stages of the algorithm based on the number of matrices in consideration (i.e., selecting skip as the first button, jumps forward to the end of computing the cost for all combinations of two matrices).

Evaluation

There is enough here that with a little effort a student could work out what the problem is and how this solution works. The visualization itself has promise, but it could be improved a great deal. There is a certain sloppiness to it that detracts from its effectiveness. The control buttons are all the wrong size, the the labels are all clipped to three letters. Some of the animation steps try to display several blocks of text, and they end up flashing on the screen without leaving the user time enough to read them. On the other hand, in an effort to really indicate where values come from, there is a fairly slow animation of the numbers sliding out of the table and into equations. Unfortunately, after a few frames of animation, the context is lost and while the number can still be seen traveling along, there is no indication where it came from. Simply highlighting the cell in the table would have been more effective. There are also a number of informative text messages that pop up in odd places, sometimes covering other parts of the display. Aesthetically, the visualization (and the website) is showing its age with the bold, multicolor approach common to the web in the 90's (particularly bad is the glaring yellow border on the visualization). I also would have liked it if the user had some control over the input data set. The data set that they have is a pretty reasonable one, but not being able to change it doesn't allow for much exploration.

Step Control; Animation; Canned Data

Lecture Aid; Self Study

Screenshots

Videos

References

First Visited

2006-11-06

Last Visited

2008-07-17

Last Updated

1998

Topic

Community

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

http://www.eecs.wsu.edu/~holder/courses/cse2320/lectures/applets/knapsack/knapsack.html

Edit

You may edit this entry if you have an account.

The Unbound Knapsack Problem

Recommendation

Unrated

Link

Delivery Method

JavaScript

License

Language

English

Author

Lawrence Holder

Institution

University of Texas, Arlington

Project

StandAlone

StandAlone

Works

Yes

Description

The example describes the Unbounded Knapsack problem - an example of Dynamic Programming. The user is able to define the total volume of the knapsack and all the values and volumes of items of which to select things inside knapsack. The applet will then show the optimal solution.

Evaluation

The problem is well described and thus the user knows what to do. The formal definition of the algorithm doing the solution is also described lower in the page. The given visualization example does not however visualize the run of the algorithm, but only runs the algorithm through showing the optimal solution. The main point is that the user is able to define the input for the algorithm (the volumes and values of the items). As the use is then based only on the 'Solve' button and a given optimal solution, the user can easily just start 'playing' with different inputs without focusing at all on one run. What is good, is that the calculations of the algorithm are shown below, but in a too small text area that is too easily left hidden. This is an interesting applet, a 'nice to play with', but should really visualize the run of the algorithm with the ability for the user to control the run (step-by-step) in order to actually help the learning experience.

Exploring the Concept

Screenshots

Videos

References

First Visited

Last Visited

2008-06-12

Last Updated

Topic

Community

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

http://alvie.algoritmica.org/

Edit

You may edit this entry if you have an account.

ALVIE - Dynamic Programming (Fibonacci)

Recommendation

Unrated

Link

Delivery Method

Java Application

License

By Request

Language

English

Author

Pilu Crescenzi

Institution

University of Florence

Project

ALVIE

Works

Yes

Description

Walkthrough showing a dynamic programming algorithm for computing a number in the Fibonacci sequence.

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/fibonacci.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