Below are my subject evaluations of all the animations included with xtango. I have rated them on a scale from 0 to 10, with 0 meaning unusable and 10 meaning Oscar material. My primary criteria is usefulness in explaining the algorithm, but I give points for gratuitous slick presentation as well. Enjoy! Steven Skiena April 2, 1996 ====================================================================== * Resource allocation allocator illustrates a resource allocation strategy Not that interesting. (3) * Goofy animations anim illustrates some of the graphics and animation capabilities of Tango Interesting to watch, but devoid of meaning. (2) * AVL trees avl illustrates operations on AVL trees Type in an increasing sequence of numbers and watch the changes. Effective animation, even though (or perhaps because) it is graphically simple. (6) * Binomial heaps binoheap illustrates ops on a binomial heap data structure Interesting and effective animation. (7) * Binary Trees bintree illustrates ops on a binary tree OK - not very robust. (4) * Boyer-Moore string matching boyer illustrates the Boyer-Moore string matching algorithm Slick-looking and perhaps effective. (7) * Bin-packing bpack illustrates first-fit bin packing algorithm Kind of interesting to watch - crashed when full. (6) * Bresenham's line drawing algo bres illustrates Bresenham's algorithm for scan converting lines Very interesting to watch, and well-designed to be informative. (7) * Binary search bsearch illustrates the binary search algorithm OK - not that exciting. (4) * Bubble sort bsort illustrates the bubble sort algorithm in vintage algo anim fashion The classic moving-bars algorithm animation. Worth seeing once. (7) * B-trees btree illustrates operations on b-trees Dumps core instantly. (1) * Bubble sort bubsort illustrates the bubble sort algorithm as a pile of blocks Horizontal bars -- I like bsort better. (5) * Polygon clipping clip illustrates clipping a polygon against a rectangle Nice animation of clipping, with interactive mode to create an instance. (6) * Graph colorability color illustrates a brute-force recursive graph colorability algo Backtracking procedure to find the coloring. Interactive mode permits mouse input of the graph. (6) * Combsort algorithm combsort illustrates the combsort algorithm I don't recall ever hearing of combsort, but it seems a lot like shell sort. Easy to watch animation. (6) * Convex Hull conhull illustrates the Jarvis march convex hull algorithm Simple but effective implementation of Jarvis march. (6) * Deterministic finite automata dfa illustrates the operations of a dfa A cumbersome and not-very robust simulation of a DFA on an input string. (3) * Depth-first search dfs illustrates the depth-first search algorithm Easy-to-watch but uninformative animation of DFA in action. (4) * Dijkstra's algorithm dijkstra illustrates dijkstra's shortest path algorithm Slightly perplexing but reasonable animation of Dijkstra's algorithm. (5) * UNIX directory visualizer dirviz visualizes directory structures using treemap technique More a tool than an animation. I'll stick with ls. (3) * Computing factorials fact illustrates calculation of the factorial function OK animation of recursion. (4) * Fast Fourier transform fft illustrates the Fast Fourier transformation I'm not 100% sure what is going on, but this is one of the most exciting animations of the bunch. (8) * Fibonacci Heaps fiboheap illustrates operation on a Fibonacci heap data structure Interesting and informative animation, worth comparing with binoheap. (7) * Shortest path floydwar illustrates the Floyd-Warshal shortest path algorithm Easy to watch and potentially instructive animation. (6) * The Game of Life gameoflife illustrates the game of life simulation Generic game of life simulation. (4) * Genetic TSP algorithm gen illustrates a genetic algorithm for solving travelling salesman Fun to watch, and sufficiently slow to converge to kill ones interest in genetic algorithms. (6) * ??? ghost visualization of something about lines and angles in the plane Finds a non-intersecting matching of red-blue points. Fun to watch. (6) * Graham scan graham illustrates a Graham scan convex hull algorithm A fine animation of graham scan in action. (7) * Towers of Hanoi problem hanoi visualization of the Towers of Hanoi problem (pegs & disks) Standard puzzle, possibly useful in understanding recursion and exponential growth. (5) * Hashing hash illustrates hashing A nice, complete animation of linear probing, with insertions and deletions supported as well as queries. (6) * Heap sorting heap illustrates a heap sort algorithm Elegant and effective animation of heapsort. (7) * Hilbert Curves hilbert shows how hilbert curves are drawn Nice animation which shows the recursive nature of the construction. (6) * Knuth-Morris-Prat string matching kmp illustrates the KMP string matching algorithm Not very descriptive, unfortunately. (4) * Kepler's Laws kepler illustrates Kepler's Laws of Planetary motion Watchable but unclear to me what is was supposed to show. (3) * Knight's tour knight illustrates a knight's tour on a chessboard (recursion & backtrack) Very cute and instructive animation. Illustrates backtracking by constructing all possible tours of the chess board. (7) * Kruskal's MST algorithm kruskal illustrates kruskal's minimum spanning tree algorithm Permits the user to enter a graph and display the MST -- not really an animation of the algorithm. (3) * K-Selection ksel illustrates linear algorithm for choosing kth biggest element from set Instructive animation of linear time selection -- uses text as well as images. (7) * Linked lists list illustrate operations on a linked list (real nice one) Slick looking animation of simple list insertion and deletion. (6) * Matrix multiplication matrixmult illustrates how matrix multiplication works Simple animation of $O(n^3)$ matrix multiplication. (4) * Merge sort merge illustrates merging of two sorted lists Simple animation of list merging. (5) * Pairing Heaps pairheap illustrates operations on a two-pass pairing heap data structure Not very robust - could use an input file. (4) * Producer-Consumer problem pc illustrates functioning of a producer-consumer-monitor ring buffer Flashy if uninformative animation. (3) * Reverse Polish notation calculator pol_calc illustrates how a RPN calculator works Probably would be more informative with a display of the formula being crunched. (3) * Polygon scan conversion polyscan illustrates scan-converting a polygon I couldn't make this one work. (0) * Post office problem post illustrates queueing via the post office problem Flashy but uninformative. (3) * Postfix conversion postfix illustrates converting an infix expression to a postfix one Nicer animation than pol_calc. (4) * Prim's MST Algorithm prim illustrates Prim's minimum spanning tree algorithm Simple but effective implementation of Prim's algorithm (6) * Eight Queens problem queens illustrates 8-queens chess board problem Terrific animation of the backtraching. I wish that I had shown this in class the last time I taught backtracking. (8) * Quicksort quicksort illustrates quicksort algorithm Classic moving dots animation of quicksort. Worth watching. (7) * Quicksort quicky illustrates another view of quicksort algorithm Also instructive, possibly more so than quicksort, but I'm partial to the moving dots. (6) * Radix sort radix illustrates a radix sort Nice animation of radix sort - informative and worth watching. (7) * Random number generator random illustrates random # generation and hashing Nice illustration of non-uniformity in random number generation. (6) * Red-Black trees rbtree illustrates operations on red-black trees Actually, not bad. It just permits insertions and rebalancing. (5) * Red-Black trees rdblktree illustrates operations on red-black trees (better one) Very instructive animation, with minimalist but well chosen graphics. Supports insertion and deletion. (7) * Drunken cockroach problem roach Illustrates a drunken cockroach wandering around a pattern Nice illustration of a random walk -- the more often a square is visited the darker it gets. (5) * Shakersort shaker illustrates shakersort algorithm Moving-bar animation of a generalization of bubblesort. (5) * Shellsort shellsort illustrates shellsort algorithm Nice moving-bar animation of shellsort, a generalization of insertion sort. (6) * Card shuffling shuffle illustrates random card shuffling Moving-bar animation of shuffling, not too exciting. (3) * Shortest path algorithm spath illustrates finding the shortest path between vertices in a graph Another animation of Dijskra's algorithm. (5) * Search Tree tree illustrates building a binary search tree Random search tree construction, culminating in a core dump. (4) * Treaps treap illustrates operations on a treap data structure Instructive animation of a new and interesting data structure. (7) * Topological sort topsort illustrates a topological sort algorithm Slick-looking animation, but it is not clear which algorithm is being used, or even that the underlying graph is directed. (5) * Travelling salesman problem tsp illustrates an algorithm for the travelling salesman problem Animation of the minimum spanning tree heuristic for TSP -- would be more informative by showing the cycle and giving its length. (4) * 3D viewing transformations viewtran illustrates how 3D viewing transformations work Crashed when I ran it. (0) * Virtual memory vmem illustrates a virtual memory replacment scheme Couldn't compile it successfully. (0) * There are also some sorting algorithms (insertion and select) without their own animation views. You might want to tie them to one of the existing views (bsort, bubsort, quicksort) or make up your own.