Analysis of Algorithms

General

1. Asymptotic notation
   • Wikipedia: Big O Notation
   • NIST big-O notation
2. Master theorem
   • Wikipedia: Master theorem
   • NIST Master theorem
3. Data structures
   • Wikipedia: List of data structures
   • NIST Dictionary of Algorithms and Data Structures
4. Graph theory
   • Wikipedia: Graph theory
   • Graph Theory Tutorials
   • Graph Theory

Sorting Algorithms

1. Merge Sort
   • Wikipedia: Mergesort
   • NIST mergesort
   • Merge Sort Algorithm Simulation
     Applet to see Merge Sort in action
2. Heap Sort
   • Wikipedia: Heapsort
   • NIST heapsort
   • Heap Sort
   • Heap Sort Visualization
     An applet to see Heap Sort in action
   • Heap Sort Animation with User Input
     Another applet
3. Quick Sort
   • Wikipedia: Quicksort
   • NIST quicksort
   • Interactive Quicksort
     An applet to see Quick Sort in action
4. Selection algorithm
   • Wikipedia: Selection Algorithm
5. Lower bound of comparison sort
   • Wikipedia: Comparison sort
   • A Lower Bound on Sorting
   • Lower bound for sorting

Dynamic Programming

1. Definitions
   • Wikipedia: Dynamic programming
   • NIST Dynamic programming
   • A Tutorial on Dynamic Programming
2. Matrix chain multiplication
   • Wikipedia: Matrix chain multiplication
   • Matrix chain multiplication simulation
     An applet to see the matrix chain multiplication in cation
3. Longest common subsequence
   • Wikipedia: Longest common subsequence
   • NIST Longest common subsequence
   • Longest Common Subsequences
   • Longest common subsequences
     An applet to see the longest common subsequence in action

Graph Algorithms

1. Minimum Spanning Tree
   • Wikipedia: Minimum spanning tree
   • NIST Minimum spanning tree
   • Minimum Spanning Trees
   • Kruskal’s algorithm
   • Kruskal’s Algorithm
     Several applets to see Kruskal’s algorithm
   • Prim’s algorithm
   • Prim’s Algorithm
     Several applets to see Prim’s algorithm
   • Boruvka’s algorithm
2. Interval Graphs
   • Wikipedia: Interval graph
   • MathWorld: Interval Graph
3. Dijkstra’s algorithm
   • Wikipedia: Dijkstra’s algorithm
   • NIST Dijkstra’s algorithm
   • Dijkstra’s Algorithm
   • Dijkstra’s Algorithm
     Several applets to see Dijkstra’s algorithm
4. Network flow
   • Wikipedia: Network flow
   • Network Flow
   • Network flow problems
   • Ford-Fulkerson Algorithm
     Applet to see the Ford-Fulkerson algorithm

Geometry

1. Voronoi Diagram/Delaunay triangulation
   • Wikipedia: Voronoi diagram
   • Wikipedia: Delaunay triangulation
   • Delaunay Triangulation
   • Voronoi/Delaunay Applet
     An applet to construct Voronoi diagrams and Delaunay triangulations
2. Euclidean minimum spanning tree
   • Wikipedia: Euclidean minimum spanning tree

 Imprimir página