CMU 15-451 (Algorithms), Spring 2009

Instructor: Manuel Blum

TAs: David Abraham, Pranjal Awasthi, Maxim Makatchev, Daniel Nuffer

General info

Practice Exams




Lecture notes [The first 10 lectures] [The next 10 lectures]

  1. 01/13:Intro & Admin. Karatsuba/Strassen.
    01/14: (recitation) Warmup problems.
  2. 01/15:Asymptotic analysis, solving recurrences.
  3. 01/20:Probabilistic analysis, Randomized Quicksort.
    01/21: (recitation) Problems related to randomized quicksort.
  4. 01/22:Linear-time Selection (randomized and deterministic).
  5. 01/27:Comparison-based lower bounds for sorting.
    01/28: (recitation) Problems related to selection recurrence, upper/lower bounds in concrete models.
  6. 01/29:Concrete models and tight upper/lower bounds
  7. 02/03:Amortized Analysis
    02/04: (recitation) Go over hwk1. Problems related to tight bounds and minimax optimality.
  8. 02/05:Search trees: B-trees and treaps.
  9. 02/10:Digit-based sorting/data-structures (radix sort, tries).
    02/11: (recitation) B-tree and treap examples, treap analysis.
  10. 02/12:Universal and Perfect Hashing.
  11. 02/17:Dynamic Programming.
    10/01: (recitation) Hashing and DP review.
  12. 02/19:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
  13. 02/24:Graph Algorithms II: Dijkstra, Prim, Kruskal.
    02/25: (recitation) Maximum bottleneck path, coupon-collector's problem.
  14. 02/26: review.
  15. 03/03: Midterm
  16. 03/05:Graph Algorithms III: Union-find.
  17. 03/17:Fun with BFS and DFS.
    03/18: (recitation)2-coloring,BFS and DFS trees.
  18. 03/19:Network Flows and Matchings I.
  19. 03/24:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
    03/25: (recitation) Examples of problems that can be solved using network flow.
  20. 03/26:Linear Programming.
  21. 10/31:NP-completeness I.
    04/01: (recitation) Examples of problems that can be solved using linear programming.
  22. 04/02:NP-completeness II.
    04/08: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.
  23. 04/09:Approximation Algorithms.
  24. 04/14:Online Algorithms.
  25. 04/21:Number theoretic algorithms I.
    Number theoretic algorithms II.
    04/22: (recitation) More NP-completeness and number theory.
  26. 04/23:Fast Fourier Transform (FFT).
  27. 04/28:Intro to machine learning theory.
    04/29: (recitation) FFT, review.