Analysis of Algorithms

General

1. Asymptotic notation
   • Wikipedia: Big O Notation ^[1]
   • NIST big-O notation ^[2]
2. Master theorem
   • Wikipedia: Master theorem ^[3]
   • NIST Master theorem ^[4]
3. Data structures
   • Wikipedia: List of data structures ^[5]
   • NIST Dictionary of Algorithms and Data Structures ^[6]
4. Graph theory
   • Wikipedia: Graph theory ^[7]
   • Graph Theory Tutorials ^[8]
   • Graph Theory ^[9]

Sorting Algorithms

1. Merge Sort
   • Wikipedia: Mergesort ^[10]
   • NIST mergesort ^[11]
   • Merge Sort Algorithm Simulation ^[12]
     Applet to see Merge Sort in action
2. Heap Sort
   • Wikipedia: Heapsort ^[13]
   • NIST heapsort ^[14]
   • Heap Sort ^[15]
   • Heap Sort Visualization ^[16]
     An applet to see Heap Sort in action
   • Heap Sort Animation with User Input ^[17]
     Another applet
3. Quick Sort
   • Wikipedia: Quicksort ^[18]
   • NIST quicksort ^[19]
   • Interactive Quicksort ^[20]
     An applet to see Quick Sort in action
4. Selection algorithm
   • Wikipedia: Selection Algorithm ^[21]
5. Lower bound of comparison sort
   • Wikipedia: Comparison sort ^[22]
   • A Lower Bound on Sorting ^[23]
   • Lower bound for sorting ^[24]

Dynamic Programming

1. Definitions
   • Wikipedia: Dynamic programming ^[25]
   • NIST Dynamic programming ^[26]
   • A Tutorial on Dynamic Programming ^[27]
2. Matrix chain multiplication
   • Wikipedia: Matrix chain multiplication ^[28]
   • Matrix chain multiplication simulation ^[29]
     An applet to see the matrix chain multiplication in cation
3. Longest common subsequence
   • Wikipedia: Longest common subsequence ^[30]
   • NIST Longest common subsequence ^[31]
   • Longest Common Subsequences ^[32]
   • Longest common subsequences ^[33]
     An applet to see the longest common subsequence in action

Graph Algorithms

1. Minimum Spanning Tree
   • Wikipedia: Minimum spanning tree ^[34]
   • NIST Minimum spanning tree ^[35]
   • Minimum Spanning Trees ^[36]
   • Kruskal’s algorithm ^[37]
   • Kruskal’s Algorithm ^[38]
     Several applets to see Kruskal’s algorithm
   • Prim’s algorithm ^[39]
   • Prim’s Algorithm ^[40]
     Several applets to see Prim’s algorithm
   • Boruvka’s algorithm ^[41]
2. Interval Graphs
   • Wikipedia: Interval graph ^[42]
   • MathWorld: Interval Graph ^[43]
3. Dijkstra’s algorithm
   • Wikipedia: Dijkstra’s algorithm ^[44]
   • NIST Dijkstra’s algorithm ^[45]
   • Dijkstra’s Algorithm ^[46]
   • Dijkstra’s Algorithm ^[47]
     Several applets to see Dijkstra’s algorithm
4. Network flow
   • Wikipedia: Network flow ^[48]
   • Network Flow ^[49]
   • Network flow problems ^[50]
   • Ford-Fulkerson Algorithm ^[51]
     Applet to see the Ford-Fulkerson algorithm

Geometry

1. Voronoi Diagram/Delaunay triangulation
   • Wikipedia: Voronoi diagram ^[52]
   • Wikipedia: Delaunay triangulation ^[53]
   • Delaunay Triangulation ^[54]
   • Voronoi/Delaunay Applet ^[55]
     An applet to construct Voronoi diagrams and Delaunay triangulations
2. Euclidean minimum spanning tree
   • Wikipedia: Euclidean minimum spanning tree ^[56]

^[57] Imprimir página ^[57]