CMU 15-451 (Algorithms), Fall 2008

Instructor: Avrim Blum

TAs: Sameer Chopra, Matt Delaney, Jim Spagnola, Jenn Tam, Daegun Won

General info

• Lectures: Tue/Thu 12-1:20, Wean 7500.
• Recitations:
  • A: Wed 12:30, SH 208 (TA: Sameer Chopra)
  • B: Wed 1:30, WeH 5312 (TAs: Daegun Won and Jim Spagnola)
  • C: Wed 2:30, SH 219 (TA: Jenn Tam)
  • D: Wed 12:30, CFA 211 (TA: Matt Delaney)
• Course information
• Schedule
• The course bboards are: academic.cs.15-451 (for announcements) and academic.cs.15-451.discuss (for general discussion).

Minis

• Mini 1. Due midnight Sept 2.
• Mini 2. Due midnight Sept 16.
• Mini 3. Due midnight Sept 30.
• Mini 4. Due midnight Oct 28.
• Mini 5. Due midnight Nov 25.

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 [ps, pdf]. Solutions [ps, pdf].

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

1. 08/26:Intro & Admin. Karatsuba/Strassen.
   08/27: (recitation) Warmup problems.
   
2. 08/28:Asymptotic analysis, solving recurrences.
   
3. 09/02:Probabilistic analysis, Randomized Quicksort.
   09/03: (recitation) Problems related to randomized quicksort, insertion sort.
   
4. 09/04:Linear-time Selection (randomized and deterministic).
   
5. 09/09:Comparison-based lower bounds for sorting.
   09/10: (recitation) Problems related to selection recurrence, upper/lower bounds in concrete models.
   
6. 09/11:Concrete models and tight upper/lower bounds
   
7. 09/16:Amortized Analysis
   09/17: (recitation) Common problems in hwk1, problems related to tight bounds and minimax optimality.
   
8. 09/18:Search trees: B-trees and treaps.
   
9. 09/23:Digit-based sorting/data-structures (radix sort, tries).
   09/24: (recitation) B-tree and treap examples, treap analysis.
   
10. 09/25:Universal and Perfect Hashing.
    
11. 09/30:Dynamic Programming.
    10/01: (recitation) Hashing and DP review.
    
12. 10/02:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
    
13. 10/07:Graph Algorithms II: Dijkstra, Prim, Kruskal.
    10/08: (recitation) Maximum bottleneck path, coupon-collector's problem.
    
14. 10/09: review.
    10/15: (recitation) 2-coloring, BFS and DFS trees.
    
15. 10/16:Graph Algorithms III: Union-find.
    
16. 10/21:Network Flows and Matchings I.
    10/22: (recitation) Examples of problems that can be solved using network flow.
    
17. 10/23:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
    
18. 10/28:Linear Programming.
    10/29: (recitation) Examples of problems that can be solved using linear programming.
    
19. 10/30:NP-completeness I.
    11/04: - no class today -
    11/05: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.
    
20. 11/06:NP-completeness II.
    
21. 11/11:Approximation Algorithms.
    
22. 11/13:Online Algorithms.
    
23. 11/18:Number theoretic algorithms I.
    11/19: (recitation) More NP-completeness and number theory.
    
24. 11/20:Number theoretic algorithms II.
    
25. 11/24:Fast Fourier Transform (FFT).
    
26. 12/02:Intro to machine learning theory.
    
27. 12/04:Intro to game theory.