Monday, May 2, 2011

More Algorithm Visualizations

  A little over a week ago I wrote a post about a college in Europe that used Hungarian folk dance to explain a few basic sorting algorithms. Today, I ran into another site that does an excellent job showing exactly how different algorithms work, maybe not with as much toe tapping as with the folk dance but effective none the less. Associate Professor David Galles from the University of San Francisco filled his site with java script animations of various algorithms, each very important for a solid base in computer science.
  First are data structures such as queues and stacks, where you can push values into the structure and pop them off. Stacks are extremely important for programming as they are used to keep track of function calls (when a new function is called, it is placed on top of the calling function. The called function performs its tasks and then is popped off the stack, giving precedence back to the calling function). Queues can be used as a method of resource allocation, giving out resources in a first come first serve approach (which is a method that is far too basic for real resource allocation, but that's not the point).
  Indexing is a complex issue dealing with storing and retrieving information. Given a piece of information, what is the best way to store it quickly while being able to retrieve it just as quickly. Each method uses a different point from which to start from and then moves from there, such as the binary tree uses the first node as a root node and uses comparisons to place additional data, passing it down the left when it is smaller than the current node or to the right if it is larger. Hash mapping uses the value of the data to place it in different bins, where hopefully it's quicker to step through a portion of the data than the entire set of data.
  The sorting algorithms are mostly what I've showed before with a few new ones added. Radix and bucket sort are pretty interesting fare, using number placement as well as value for sorting the values. A problem that arises with these new sorting algorithms is they require additional resources to hold partially sorted data, increasing overhead costs. Heaps are a type of data storage that keeps the largest value as the root node, with each child smaller than its parents and can be used as a sorting structure using heapsort.
  The graph algorithms are used when given a graph of nodes with some sort of cost associated with moving between nodes. A depth first search will find a path between a start and an end node by moving until it reaches a dead end, then backtracks to the previous node until it finds a different route. A breadth first search sends out paths every direction, each level of depth being explored simultaneously. Dijkstra's and Prim's algorithms are generally used to find shortest or least costly paths between two nodes. I found another site that gives a good visualization on how Dijkstra's algorithm works.
  These visualizations can give an excellent view in to how these algorithms actually function. Playing around with them can help clear up any uncertainties on how these algorithms work, so give it a shot.

1 comment:

  1. The USFCA site is impressive.

    I’ve also put up some Visualizations which could be used to assist in teaching an introductory programming or data structures course :

    Yet to add some more supporting text and a few more applets.