CMU 15-451 (Algorithms), Fall 2005

Instructor: Avrim Blum

TAs: David Abraham, Mihir Kedia, Katrina Ligett, and Matt Streeter

Announcements

• Review session: Wednesday Dec 14, 1:00-3:00pm in Wean 7500.
• Here is last year's final exam for practice [ps, pdf].
• The final exam is Tues Dec 20, 8:30-11:30am, in McConomy Auditorium. The final will be closed book, 1 sheet of notes allowed.

General info

• Lectures: Tue/Thu 12-1:20, Wean 7500.
• Recitations: Wed 12:30/1:30/2:30/12:30. (A,B,C in SH 219; D in DH 1209).
• 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 6.
• Mini 2. Due midnight Sept 20.
• Mini 3. Due midnight Oct 4.
• Mini 4. Due midnight Nov 1.
• Mini 5. Due midnight Dec 1.

Homeworks

• Homework 1 [ps, pdf]. Due (start of class) Sept 13. Solutions [ps, pdf].
• Homework 2 [ps, pdf]. Due Sept 27/28 (oral presentations). Solutions [ps, pdf].
• Homework 3 [ps, pdf]. Due (start of class) Oct 11. Solutions [ps, pdf].
• Homework 4 [ps, pdf]. Due Oct 26/27 (oral presentations). Solutions [ps, pdf].
• Homework 5 [ps, pdf]. Due (start of class) Nov 8. Solutions [ps,pdf]
• Homework 6 [ps, pdf]. Due Nov 21/22 (oral presentations). Solutions [ps, pdf].
• Homework 7 [ps, pdf]. Due (start of class) Dec 8. Solutions [ps, pdf].

Lecture notes

1. 08/30:Intro & Admin. Karatsuba/Strassen. [ps][pdf]
   08/31: (recitation) Warmup problems.
   
2. 09/01:Asymptotic analysis, solving recurrences.
   
3. 09/06:Probabilistic analysis, Randomized Quicksort.
   09/07: (recitation) Insertion sort and inversions. Section B [pdf].
   
4. 09/08:Linear-time Selection (randomized and deterministic).
   
5. 09/13:Lower bounds for comparison-based sorting.
   
6. 09/15:Concrete models of computation and tight upper/lower bounds
7. 09/20:Amortized Analysis
   09/21: (recitation) Amortized analysis + Go over practice quiz.
   
8. 09/22:Search trees: B-trees and treaps.
   
9. 09/27:Digit-based sorting/data-structures (radix sort, tries).
   
10. 09/29:Universal and Perfect Hashing.
    
11. 10/04:Dynamic Programming.
    
12. 10/06:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
    
13. 10/11:Graph Algorithms II: Dijkstra, Prim, Kruskal.
    10/12: (recitation) Kruskal and union-find.
    
14. 10/13:Midterm review
15. 10/20:Graph Algorithms III: coloring, strongly-connected components.
    
16. 10/25:SCC contd, Network Flows and Matchings I.
    10/26:More flows and matchings.
    
17. 10/27:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
    
18. 11/01:Linear Programming.
    11/02: (recitation) Practice with Flows and LPs.
    
19. 11/03:NP-completeness I.
    
20. 11/08:NP-completeness II.
    11/09: (recitation) Practice with NP-completeness.
    
21. 11/10:Approximation Algorithms.
    
22. 11/15:Online Algorithms.
    
23. 11/17:Number theoretic algorithms I.
    
24. 11/22:Number theoretic algorithms II.
    
25. 11/29:Fast Fourier Transform (FFT).
    
26. 12/01:Fair division: fair and envy-free cake-cutting.
    
27. 12/06:Intro to game theory [ppt][pdf].
    
28. 12/08:Learning Finite-State Environments.