CMU 15-451/651 (Algorithms), Fall 2012

Instructors: Avrim Blum and Daniel Sleator

TAs: Andrew McKinnie, Dennis Meng, Ankit Sharma, Carol Wang, John Wright, Patrick Xia, Fan Xiang


General info


Minis


Homeworks


Lecture & recitation notes [Lectures 1-5]

Readings given as [CLRS/DPV].
  1. 08/28:Intro & Admin. Karatsuba/Strassen.
    08/29: (recitation) Warmup problems.
  2. 08/30:Asymptotic analysis, solving recurrences. [Ch 1-4/Ch 0,1.1,2.1-2.2]
  3. 09/04:Probabilistic analysis, Randomized Quicksort. [Ch 5,7/-] [Mini 1 due]
    09/05: (recitation) Problems related to randomized quicksort, insertion sort.
  4. 09/06:Linear-time Selection (randomized and deterministic), sorting lower bounds. [Ch 8.1,9/Ch 2.4]
  5. 09/11:Concrete models and tight upper/lower bounds. [Hwk 1 due]
    09/12: (recitation) Problems related to selection, tight upper/lower bounds.
  6. 09/13:Game Theory. [-/Ch 7.5]
  7. 09/18:Universal and Perfect Hashing. [Ch 11/Ch 1.5] [Mini 2 due]
    09/19: (recitation) Hashing and prep for quiz.
  8. 09/20:Amortized Analysis (part 1, part 2, part 3) + Quiz. [Ch 17/-]
  9. 09/25:Splay trees [Hwk 2 presentations]
    09/26: (recitation) Tree rotations.
  10. 09/27:Augmenting search trees [Ch 14]
  11. 10/02:Dynamic Programming, incl shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall). [Ch 15, 24.1, 25.1-25.2/Ch 6] [Mini 3 due]
  12. 10/04:Graph Algorithms I:Depth First Search Strongly-connected components and biconnected components
  13. 10/09:Link/Cut Trees [Hwk 3 due]
    10/10: (recitation) SCCs.
  14. 10/11:Network Flows and Matchings I. [Ch 26/7.2-7.3]
  15. 10/16:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow. [Mini 4 due]
  16. 10/18: Midterm.
  17. 10/23:Matchings in general graphs. [Hwk 4 presentations]
    10/24: (recitation) Flows and cuts.
  18. 10/25:Linear Programming I. [Ch 29/Ch 7.1,7.6]
  19. 10/30:NP-completeness I. [Ch 34/Ch 8]
    10/31: (recitation) Linear programming and NP-completeness examples.
  20. 11/01:NP-completeness II.
  21. 11/06:Approximation Algorithms. [Ch 35/Ch 9.2] [Hwk 5 due]
    11/07: (recitation) Go over practice quiz. NP-completeness examples.
  22. 11/08:Linear Programming II. [Ch 29/Ch 7.4]
  23. 11/13:Online Algorithms+ Quiz.
    11/14: (recitation) More on complexity classes.
  24. 11/15:Machine Learning, online learning algorithms.
  25. 11/20:Two Algorithms for Closest Pair [O(n) expected] [O(n log n)] [Hwk 6 presentations]
  26. 11/27:String Matching I.
  27. 11/29:Fast Fourier Transform (FFT). [Ch 30/Ch 2.6] [Mini 5 due]
  28. 12/04:String Matching II, Suffix Trees [TXT,PDF]
  29. 12/06:Shortest Common Superstring (not on test). [Hwk 7 due]