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

• Lectures: Tue/Thu 12-1:20, DH 2210
• Recitations:
  • A: Wed 10:30 (BH 136A) - Patrick Xia [pjx@cs]
  • B: Wed 11:30 (WEH 4709) - Fan Xiang [fxiang@andrew]
  • C: Wed 12:30 (WEH 4709) - Andrew McKinnie [amckinni@andrew]
  • D: Wed 2:30 (WEH 5421) - John Wright [jswright@cs]
  • E: Wed 3:30 (DH 2105) - Dennis Meng [dmeng@andrew]
  • F: Wed 9:30 (DH 1117) - Ankit Sharma [ankits@cs]
  • G: Wed 4:30 (GHC 4211) - Carol Wang [carolwan@cs]
• Course information
• Final exam: the registrar has scheduled our final exam to be Dec 17 8:30am-11:30am (one of the 15-651 sections somehow lists an incorrect date).

Minis

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

Homeworks

• Homework 1. Solutions.
• Homework 2. Solutions.
• Homework 3. Solutions. Clarification: on problem 1, you can use a 3rd stack to temporarily store elements being transferred between the two main stacks.
• Homework 4. Solutions.
• Homework 5. Solutions.
• Homework 6. Solutions.
• Homework 7. Solutions.

Lecture & recitation notes [Lectures 1-5]

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]