CMU 15-451 (Algorithms), Fall 2009

Instructor: Avrim Blum

TAs: Vicki Cheung, Sameer Chopra, Khalid El-Arini, Jiri Simsa, Zizhuang Yang

General info

• Lectures: Tue/Thu 12-1:20, GHC 4401.
• Recitations:
  • A: Wed 10:30 (BH 136A) - Zizhuang Yang
  • B: Wed 11:30 (GHC 4215) - Sameer Chopra
  • C: Wed 9:30 (HBH 1002) - Vicki Cheung
  • D: Wed 2:30 (WEH 4623) - Khalid El-Arini
  • E: Wed 3:30 (GHC 4211) - Jiri Simsa
• Course information
• Schedule
• How to sign up for the course bboards

Minis

• Mini 1. Due midnight Sept 1.
• Mini 2. Due midnight Sept 15.
• Mini 3. Due midnight Oct 1.
• Mini 4. Due midnight Oct 27.
• Mini 5. Due midnight Nov 24..

Homeworks

• Homework 1 [ps, pdf]. Solutions [ps, pdf].
• Homework 2 [ps, pdf]. Solutions [ps, pdf].
• Homework 3 [ps, pdf]. Solutions [ps, pdf].
• Homework 4 [ps, pdf]. Solutions [ps, pdf].
• Homework 5 [ps, pdf]. Solutions [ps, pdf].
• Homework 6 [ps, pdf]. Solutions [ps, pdf].
• Homework 7: hardcopy available outside GHC 8120. [pdf w/o attached practice test]. Due Dec 3.

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

1. 08/25:Intro & Admin. Karatsuba/Strassen.
   08/26: (recitation) Warmup problems.
   
2. 08/27:Asymptotic analysis, solving recurrences.
   
3. 09/01:Probabilistic analysis, Randomized Quicksort.
   09/02: (recitation) Problems related to randomized quicksort, insertion sort.
   
4. 09/03:Linear-time Selection (randomized and deterministic).
   
5. 09/08:Comparison-based lower bounds for sorting.
   09/09: (recitation) Problems related- to selection recurrence, upper/lower bounds in concrete models.
   
6. 09/10:Concrete models and tight upper/lower bounds
   
7. 09/15:Amortized Analysis
   09/16: (recitation) problems related to tight bounds and minimax optimality.
   
8. 09/17:Search trees: B-trees and treaps.
   09/23: (recitation) B-tree and treap examples, treap analysis.
   
9. 09/24:Digit-based sorting/data-structures (radix sort, tries).
   
10. 09/29:Universal and Perfect Hashing.
    09/30: (recitation) Go over quiz, universal hashing recap, alternative universal hashing scheme.
    
11. 10/01:Dynamic Programming.
    
12. 10/06:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
    10/07: (recitation) matrix method and Floyd-Warshall.
    
13. 10/08:Graph Algorithms II: Dijkstra, Prim, Kruskal.
    
14. 10/13: Midterm.
    10/14: (recitation) 2-coloring, BFS and DFS trees.
    
15. 10/15:Graph Algorithms III: Union-find.
    
16. 10/20:Network Flows and Matchings I.
    10/21: (recitation) Examples of problems that can be solved using network flow.
    
17. 10/22:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
    
18. 10/27:Linear Programming.
    10/28: (recitation) Examples of problems that can be solved using linear programming.
    
19. 10/29:NP-completeness I.
    
20. 11/03:NP-completeness II.
    11/04: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.
    
21. 11/05:Approximation Algorithms.
    
22. 11/10:Online Algorithms.
    11/11: (recitation) More NP-completeness and approx algs: Set-Splitting and MAX-Exactly-3-SAT.
    
23. 11/12:Number theoretic algorithms I.
    
24. 11/17:Number theoretic algorithms II.
    11/18: (recitation) Number theory and more interesting complexity classes.
    
25. 11/19:Fast Fourier Transform (FFT).
    
26. 11/24:Intro to game theory.
    
27. 12/01:Intro to machine learning theory.
    12/02: (recitation) FFT for string matching, general course review.
    
28. 12/03:Mechanism/protocol design, cake cutting.