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

• Lectures: Tue/Thu 12-1:20, DH 2210
• Recitations:
  • A: Wed 10:30 (DH 2122) - Miguel Araujo [maraujo@cs]
  • B: Wed 11:30 (WEH 4709) - Kevin Su [ksu@andrew]
  • C: Wed 12:30 (WEH 4709) - Michael (rntz) Arntzenius [marntzen@andrew]
  • D: Wed 2:30 (DH 2122) - Eugene Choi [dechoi@andrew]
  • E: Wed 3:30 (DH 2105) - Yuzi Nakamura [ynakamur@cs]
  • F: Wed 9:30 (DH 1117) - Kristy Gardner [ksgardne@cs]
  • G: Wed 4:30 (GHC 4211) - Andrea Klein [andreakl@andrew]
  • H: Wed 2:30 (PH A22) - Paul Davis [pauldavi@andrew]
• Ask/answer questions on Piazza
• Use autolab to submit your mini solutions (and check past grades). The powerpoint "tutorial" from class (pdf).
• Course information
• Course Survey done in Lecture #1

Minis

• Mini 1. Due 11:59pm Sept 3.
• Mini 2. Due 11:59pm Sept 17.
• Mini 3. Due 11:59pm Oct 1.
• Mini 4. Due 11:59pm Oct 29.
• Mini 5. Due 11:59pm Nov 12.

Homeworks

• Homework 1. Solutions.
• Homework 2. Solutions.
• Homework 3. Solutions.
• Homework 4. Solutions.
• Homework 5. Solutions.
• Homework 6. Solutions.
• Homework 7. Solutions. and practice test.

Bonus Problems

• Bonus Problems 1.

Lecture & recitation notes [Lectures 1-3]

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.

More info