Algorithms

  • [1] Asymptotic Complexity

    • Growth of functions: Ordering functions
    • Asymptotic notations: Big-Oh, Big-Omega and Big-Theta
    • Running time of programs
  • [2] Divide and Conquer

    • Recurrence relation
    • Master theorem
    • Binary search
    • Integer multiplication
    • Polynomial multiplication
  • [3] Sorting

    • Insertion sort
    • Selection sort
    • Bubble sort
    • Merge sort
    • Quicksort
    • Heapsort
    • Radix sort
  • [4] Expression Parsing

    • Expression notations: Infix, Prefix, Postfix
    • Expression evaluation: Postfix evaluation
  • [5] Hashing

    • Hash tables
    • Hash functions
    • Open addressing
  • [6] Greedy Algorithms

    • Huffman coding
  • [7] Dynamic Programming

    • Matrix-chain multiplication
    • Longest common subsequence (LCS)
    • Optimal binary search trees
  • [8] Graph Search

    • Breadth-first search (BFS)
    • Depth-first search (DFS)
    • Topological sort
  • [9] Graph Connectivity

    • Minimum spanning tree (MST)
    • Kruskal's algorithm
    • Prim's algorithm
  • [10] Shortest Paths

    • Dijkstra's algorithm
    • Bellman-Ford algorithm
    • Floyd-Warshall algorithm
  • [11] Medians and Selection

    • Minimum and Maximum
    • Linear-time selection
  • Randomized Algorithms
  • Amortized Analysis
  • String Matching

    • Rabin-Karp algorithm
    • Knuth-Morris-Pratt algorithm
  • Computational Geometry

    • Convex hull
  • NP-Completeness
Go to Home