THIS SITE HAS BEEN DEDICATED TO UCSD MATH 188, WINTER 2000 DESIGN AND ALGORITHMS

STUDENTS: Kenny Ton: [email protected] and Hung Bui: [email protected]

• The followings are sorting algorithm animations.

• 1a. This is Insertion Sort animation (with user inputs)
  
  • Linked definition
    
    • Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted.
  • Run time
    • O(n2).
  • I like 1a because this animation because it accepts users inputs and shows time comlexity too.
• 1b. This is Insertion Sort animation (without user inputs)
  
  • Linked definition
    
    • Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted.
  • Run time
    • O(n2).
  • I don't like animation because it does not accept user inputs.
• 1c. This is Insertion Sort animation
  
  • Linked definition
    
    • Sort by repeatedly taking the next item and inserting it into the final data structure in its proper order with respect to items already inserted.
  • Run time
    • O(n2).
  • I don't like animation because it is hard to use.
• 2a. This is Quick Sort animation (with user inputs)
  
  • Linked definition
    
    • An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.
  • Run time
    • best case time estimate of O(N*log(N)).
    • worst-case time estimate of O(N^2).
    • it can be proved that quicksort takes O(N*log(N)) comparisons in the average-case too.
  • I like this animation because it accepts user inputs while the the next one does not.
• 2b. This is Quick Sort animation (without user inputs)
  
  • Linked definition
    
    • An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.
  • Run time
    • best case time estimate of O(N*log(N)).
    • worst-case time estimate of O(N^2).
    • it can be proved that quicksort takes O(N*log(N)) comparisons in the average-case too.
  • I don't like this animation because it does not accept user inputs.
• 2c. This is Quick Sort animation
  
  • Linked definition
    
    • An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.
  • Run time
    • best case time estimate of O(N*log(N)).
    • worst-case time estimate of O(N^2).
    • it can be proved that quicksort takes O(N*log(N)) comparisons in the average-case too.
  • I don't like this animation because it does not show any definitions and the source code.
• 3a. This is Selection Sort animation (with user input)
  
  • Linked definition
    
    • An algorithm which orders items by repeatedly looking through remaining items to find the least one and moving it to a final location.
  • Run Time
    • worst case complexity is O(N^2).
  • I like this animation because it accepts user inputs.
• 3b. This is Selection Sort animation (without user input)
  
  • Linked definition
    
    • An algorithm which orders items by repeatedly looking through remaining items to find the least one and moving it to a final location.
  • Run Time
    • worst case complexity is O(N^2).
  • I don't like this animation because it does not accept user inputs.
• 3c. This is Selection Sort animation
  
  • Linked definition
    
    • An algorithm which orders items by repeatedly looking through remaining items to find the least one and moving it to a final location.
  • Run Time
    • worst case complexity is O(N^2).
  • I don't like this animation because it does not include user inputs and it is hard to follow.
• 3d. This is Selection Sort animation
  
  • Linked definition
    
    • An algorithm which orders items by repeatedly looking through remaining items to find the least one and moving it to a final location.
  • Run Time
    • worst case complexity is O(N^2).
  • I don't like this animation because users have no control over it, it just runs by itself.
• 4a. This is Heap Sort animation (with user inputs)
  
  • Linked definition
    
    • An algorithm to sort by building a heap, then repeatedly extracting the maximum item.
  • Run Time
    • worst-case time complexity of O(n*log(n)).
  • I like this animation because it shows the heap along with the animation and it accepts user inputs.
• 4b. This is Heap Sort animation (without user inputs)
  
  • Linked definition
    
    • An algorithm to sort by building a heap, then repeatedly extracting the maximum item.
  • Run Time
    • worst-case time complexity of O(n*log(n)).
  • I don't like this animation because it does not accept user inputs.
• 4c. This is Heap Sort animation
  
  • Linked definition
    
    • An algorithm to sort by building a heap, then repeatedly extracting the maximum item.
  • Run Time
    • worst-case time complexity of O(n*log(n)).
  • I don't like this animation because it does not accept user inputs and does not contain enough graphics.
• 4d. This is Heap Sort animation
  
  • Linked definition
    
    • An algorithm to sort by building a heap, then repeatedly extracting the maximum item.
  • Run Time
    • worst-case time complexity of O(n*log(n)).
  • I don't like this animation because it is not user friendly.
• 5a. This is Simple Sort animation (with user inputs)
  
  • Definition
    • An algorithm sorts items in order regardless of efficiency.
  • Run Time
    • N(N-1)/2 steps.
  • I like this animation because it is fast.
• 5b. This is Simple Sort animation (without user inputs)
  
  • Definition
    • An algorithm sorts items in order regardless of efficiency.
  • Run Time
    • N(N-1)/2 steps.
  • I don't like this animation because it does not accept user inputs.
• 6. This is Merge Sort animation
  
  • Linked definition
    
    • A sort algorithm which splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence.
  • Run Time
    • worst case O(n log n)
  • I like this animation because it shows the source code, definitions, then the animation.
• 7a. This is Bubble Sort animation (with user inputs)
  
  • Linked definition
    
    • Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.
  • Run Time
    • (N-1) + (N-2) + ... + 2 + 1 = N*(N-2)/2 = O(N^2).
  • I like this animation because it is very fast and graphic.
• 7b. This is Bubble Sort animation (without user inputs)
  
  • Linked definition
    
    • Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.
  • Run Time
    • (N-1) + (N-2) + ... + 2 + 1 = N*(N-2)/2 = O(N^2).
  • I don't like this animation because it does not accept user inputs.
• 8. These are animated comparisons for various sorting algorithms
  
  • I like this because it lets you pick several sorts to run concurrently and it is extremely easy to compare the speeds.
• 9. These are comparisons for various sorting algorithms
  

  • Algorithm	Strategy	Advantage	Disadvantage	Complexity
    Insertion	adjacent key comparison	order optimal quick for short lists quick on long lists if.. good for on-line sorting in-place stable	W(n) A(n)	B(n) = n-1 W(n) = n2 A(n) = n2
    ShellSort	comparison-based internal memory non-adjacent	.	analysis difficult	not known in general for increments of .... W(n) = O (?)
    MergeSort	divide & conquer comparison-based internal	order optimal	.	B(n) = A(n) = W(n) = n log n
    QuickSort	divide & conquer comparison-based internal	good A(n)	bad W(n)	B(n) = A(n) = n log n W(n) = n2
    TreeSort	comparison-based internal	good A(n)	bad W(n)	B(n) = A(n) = n log n W(n) = n2
    Selection	comparison internal	.	inefficient	B(n) = A(n) = W(n) =
    HeapSort	comparison internal for priority queue	order optimal	same whether items distinct or not	B(n) = A(n) = W(n) = insert W(n) = log n adjust W(n) =log n - log i make W(n) = log n
    BingoSort	comparison-based internal m distinct items	efficient for lists with repeats better than Heapsort when m < log n	.	W(n) = A(n) = mn B(n) =
    RadixSort	internal depends on items	.	.	for string len k, W(n) = A(n) = B(n) =
    Multimerge Sort	external order optimal	.	.	W(n) =
    Multimerge SortQ	external internal priority queue	order optimal	.	W(n) =

    
    
    

    I like these comparisons because it covers almost all sorting algorithm and I find it very helpful.

  The followings are graph algorithm animations.

• 1a. This is Traveling Salesman animation
  
  • Linked definition
    
    • Find a path through a weighted graph which starts and and minimizes the total cost of edges. It is NP-complete.
  • Implementations
    • Minimum Spanning Tree costs O(N log N).
    • Incremental insertion methods.
    • K-optimal tours.
  • I like this animation because it is extremely animated and advanced.
• 1b. This is Traveling Salesman animation
  
  • Linked definition
    
    • Find a path through a weighted graph which starts and and minimizes the total cost of edges. It is NP-complete.
  • Implementations
    • Minimum Spanning Tree costs O(N log N).
    • Incremental insertion methods.
    • K-optimal tours.
  • I don't like this animation because it is hard to use and not graphical enough.
• 1c. This is Traveling Salesman animation
  
  • Linked definition
    
    • Find a path through a weighted graph which starts and and minimizes the total cost of edges. It is NP-complete.
  • Implementations
    • Minimum Spanning Tree costs O(N log N).
    • Incremental insertion methods.
    • K-optimal tours.
  • I don't like this animation because it lacks the necessary animation for an ordinary user to understand
• 2. This is Minimum Spanning Tree animation using Kruskal's algorithm
  
  • Linked definition
    
    • An algorithm for computing a minimum spanning tree. It maintains a set of partial minimum spanning trees, and repeatedly adds the shortest edge in the graph whose vertices are in different partial minimum spanning trees.
  • Implementations
    • Kruskal's algorithm costs O(M log M).
  • I like this animation because it is simple to use.
• 3. This is Minimum Spanning Tree animation using Prim's algorithm
  
  • Linked definition
    
    • An algorithm for computing a minimum spanning tree. It builds upon a single partial minimum spanning tree, at each step adding an edge connecting the vertex nearest to but not already in the current partial minimum spanning tree.
  • Implementation
    • Prim's algorithm costs O(N2).
  • I like this animation because it is simple to use.
• 4a. This is Dijkstra's Algorithm animation
  
• 4b. This is Dijkstra's Algorithm animation with variable input
  
  • Linked definition
    
    • An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. All weights must be nonnegative.
  • Performance
    • The time required by Dijkstra's algorithm is O(|V|2). It will be reduced to O(|E|log|V|) if heap is used to keep {v in V\Si : L(v) < infinity}.
  • Implementations
    • Shortest Path Algorithm costs O(N2).
    • Floyd-Warshall all-pair shortest path costs O(N3).
  • I like this animation because the java applet has a very user-friendly console in which users can effortlessly give inputs and then animate the algorithm. The variable input animation allow you to pick various graphs with different edges and vertices.
• 5. This is a backtracking algorithm for finding a Hamilton circuit animation
  
  • Linked definition
    
    • An algorithmic technique to find solutions by trying one of several choices. If the choice proves incorrect, computation backtracks or restarts at the point of choice and tries another choice. It is often convenient to maintain choice points and alternate choices using recursion. It is NP-complete.
  • Implementations
    • Longest path in Directed Acyclic Graph (DAG).
    • Reduction from Eulerian cycle.
  • I like this animation because it is fast and captures the essence of backtracking.
• 6. This is Breadth First Search animation
  
  • Linked definition
    
    • A search algorithm which considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. This is typically implemented with a queue. It is useful in shortest path problems.
  • Application
    • BFS is used to solve the Bandwidth Reduction Problem.
  • I like this animation because it is simple to follow.
• 7a. This is Depth First Search animation
  
  • Linked definition
    
    • A search algorithm which considers outgoing edges of a vertex before any neighbors of the vertex, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first. This is easily implemented with recursion.
  • Applications
    • The Euclidean Traveling Salesman Problem.
    • The Eulerian Cycle/Chinese Postman Problem.
    • The Planarity Detection and Embedding Problem.
    • The Traveling Salesman Problem.
    • The Vertex Coloring Problem.
    • The Longest Common Substring Problem.
  • I like this animation because it is simple to animate and very easy to understand because the of the slow animation speed.
• 7b. This is Depth First Search animation
  
  • Linked definition
    
    • A search algorithm which considers outgoing edges of a vertex before any neighbors of the vertex, that is, outgoing edges of the vertex's predecessor in the search. Extremes are searched first. This is easily implemented with recursion.
  • Applications
    • The Euclidean Traveling Salesman Problem.
    • The Eulerian Cycle/Chinese Postman Problem.
    • The Planarity Detection and Embedding Problem.
    • The Traveling Salesman Problem.
    • The Vertex Coloring Problem.
    • The Longest Common Substring Problem.
  • I like this animation second because because it is relative easy to use it and it is very user friendly. It captures all necessary concepts to understand the algorithm.

• This will link to many useful algorithm definitions.
  

  Dijkstra's Algorithm Animation & All Pairs Shortest Paths

  
  Dijkstra's Algorithm
• Djikstra's algorithm (named after its discover, E.W. Dijkstra) solves the problem of finding the shortest path from a point in a graph (the source) to a destination. It turns out that one can find the shortest paths from a given source to all points in a graph in the same time, hence this problem is sometimes called the single-source shortest paths problem.
• The run time for a shortest path between two vertices is O(n^2).
  
  
• This is Dijkstra's Algorithm animation
  
• This is Dijkstra's Algorithm animation with variable input
  
  

  Explaination

• In this animation, a number of cases have been selected to show all aspects of the operation of Dijkstra's algorithm. Start by selecting the data set (or you can just work through the first one - which appears by default). Then select either step or run to execute the algorithm. Note that it starts by assigning a weight of infinity to all nodes, and then selecting a source and assigning a weight of zero to it. As nodes are added to the set for which shortest paths are known, their colour is changed to red. When a node is selected, the weights of its neighbours are relaxed .. nodes turn green and flash as they are being relaxed. Once all nodes are relaxed, their predecessors are updated, arcs are turned green when this happens. The cycle of selection, weight relaxation and predecessor update repeats itself until all the shortest path to all nodes has been found.

  ALL PAIRS SHORTEST PATH

• Definition: Find the shortest paths between all pairs of vertices in a weighted, directed graph.
  
  

  COMPARISION WITH DIJISTRA'S ALGORITHM

• The all-pairs-shortest-path problem is generalization of the single-source-shortest-path problem, so we can use Floyd's algorithm, or Dijkstra's algorithm (varying the source node over all nodes). Floyd's algorithm is O(N^3) Dijkstra's algorithm with an adjacency matrix is O(N^2), so varying over N source nodes is O(N^3) Dijkstra's algorithm with adjacency lists is O(E log N), so varying over N source nodes is O(N E log N) For large sparse graphs, Dijkstra's algorithm is preferable.