CMU 15-451 (Algorithms), Spring 2010

Instructor: Manuel Blum

TAs: Dafna Shahaf, Or Sheffet, Sam Tetruashvili, Andrey Vadim Grinshpun, Tilak Sharma

General info

Practice Exams




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

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