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

Instructors: Avrim Blum and Anupam Gupta

TAs: Miguel Araujo, Michael Arntzenius, Eugene Choi, Paul Davis, Kristy Gardner, Andrea Klein, Yuzi Nakamura, Kevin Su


General info


Minis


Homeworks


Bonus Problems


Lecture & recitation notes [Lectures 1-3]

Readings given as [CLRS/DPV].
  1. 08/27:Intro & Admin. Karatsuba/Strassen. [Ch 1,2,28.2/1.1,2.1,2.5]
    08/28: (recitation) Asymptotic analysis, solving recurrences. [Ch 3,4/Ch 0,2.2]
  2. 08/29:Linear-time Selection (randomized and deterministic); recursion trees. [Ch 9/Ch 2.4]
  3. 09/03:Concrete models and tight upper/lower bounds. [Ch 8.1/Ch 2.3] [Mini 1 due]
    09/04: (recitation) Problems related to selection and concrete models.
  4. 09/05:Randomized global min-cut. [Ch 5,7/Virtual Chap - p.29, 140]
  5. 09/10:Amortized Analysis and a simple amortized dictionary data structure. [Ch 17/-] [Hwk 1 due]
    09/11: (recitation) Problems related to randomized algorithms and amortization..
  6. 09/12:Union-find (with appendix on MSTs). [Ch 21/5.1.3,5.1.4]
  7. 09/17:Universal and Perfect Hashing. [Ch 11/Ch 1.5] [Mini 2 due]
    09/18: (recitation) Quiz preparation + probability refresher.
  8. 09/19:Quiz + Basic Graph Algorithms. [Ch 22,23/Ch 3.1-3.3, 4, 5.1]
  9. 09/24: Streaming Algorithms [Hwk 2 presentations]
    09/25: (recitation) strong connected components from the 9/19 lecture.
  10. 09/26: Dynamic Programming I: knapsack, matrix product parenthesization. [Ch 15, 24.1, 25.1-25.2/Ch 6]
  11. 10/01: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and all-pairs SP (matrix, Floyd-Warshall) [Mini 3 due]
    10/02: (recitation)
  12. 10/03: Network Flows and Matchings I. [Ch 26/7.2-7.3]
  13. 10/08: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows [Hwk 3 due]
    10/09: (recitation) Flows recap, using flows to solve problems
  14. 10/10: Network Flows III: Push-relabel flow algorithms, and Min-Cost Max-Flow. (Example from class.)
  15. 10/15: Midterm.
    10/16: (recitation) Flows to solve problems II
  16. 10/17:Game Theory. [-/Ch 7.5]
  17. 10/22:Linear Programming I. [Ch 29/Ch 7.1,7.6] [Hwk 4 presentations]
    10/23: (recitation) LP and game theory examples.
  18. 10/24:Linear Programming II. [Ch 29/Ch 7.4]
  19. 10/29:NP-completeness I. [Ch 34/Ch 8] [Mini 4 due]
    10/30: (recitation) LPs and duality revision
  20. 10/31:NP-completeness II.
  21. 11/05:Approximation Algorithms. [Ch 35/Ch 9.2] [Hwk 5 due]
    11/06: (recitation) Practice quiz solutions and NP-completeness
  22. 11/07:Quiz + Online Algorithms.
  23. 11/12:Machine Learning I. [Mini 5 due]
    11/13: (recitation) Go over quiz, some problems related to SAT and online algorithms
  24. 11/14:Machine Learning II.
  25. 11/19:Fast Fourier Transform (FFT). [Ch 30/Ch 2.6] [Hwk 6 presentations]
    11/20: (recitation) Flows and games, FFTs
  26. 11/21:String Matching Algorithms. [Ch 32/?]
  27. 11/26:Auctions, VCG, incentive-aware algorithms.
  28. 12/03:Market Equilibria.
    12/04: (recitation) Suffix Trees and VCG
  29. 12/05:Matchings in General Graphs. [Hwk 7 due]
    Final exam: Friday December 13, 2013, 8:30-11:30am, McConomy.