CMU 15-451 (Algorithms), Fall 2004

Instructors: Avrim Blum, Manuel Blum

TAs: Doru Balcan, Nina Balcan, Jon Derryberry, Runting Shi

Announcements

• Our final exam is Fri Dec 17, 1-4pm, and will be in DH 2210. One sheet of notes allowed (but closed-book).
• For practice, here is last year's final. Here are solutions.
• Graded homework #7's are in the course secretary's office, Wean 4116.
• Here are solutions to quiz 2.

General info

• 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 7.
• Mini 2. Due midnight Sept 21.
• Mini 3. Due midnight Oct 5.
• Mini 4. Due midnight Nov 2.
• Mini 5 [ps, pdf]. Due midnight Dec 2.

Homeworks

• Homework 1 [ps, pdf]. Due (in class) Sept 14. Solutions [ps, pdf].
• Homework 2 [ps, pdf]. Due Sept 28/29 (oral presentations). Solutions [ps, pdf].
• Homework 3 [ps, pdf]. Due (in class) Oct 12. Solutions [ps, pdf].
• Homework 4 [ps, pdf]. Due Oct 26/27 (oral presentations). Solutions [ps, pdf].
• Homework 5 [ps, pdf]. Due (in class) Nov 9. Solutions [ps]
• Homework 6 [ps, pdf]. Due Nov 22/23 (oral presentations). Solutions [ps, pdf].
• Homework 7 [ps, pdf]. Due (in class) Dec 9. Solutions [ps, pdf].

Lecture notes

1. 08/31:Intro & Admin. Karatsuba/Strassen.
   09/01: (recitation) Warmup problems.
   
2. 09/02:Asymptotic analysis, solving recurrences.
   
3. 09/07:Probabilistic analysis, Randomized Quicksort.
   09/08: (recitation) Insertion sort and inversions.
   
4. 09/09:Linear-time Selection (randomized and deterministic).
   
5. 09/14:Upper and lower bounds in simplified models of computation.
   
09/15: (recitation) Review + Coupon collector's problem.

6. 09/16:Upper and lower bounds (II)
   
7. 09/21:Amortized Analysis
   
09/22: (recitation) Amortized analysis + Practice Quiz.

8. 09/23:Search trees: B-trees and treaps.
   
9. 09/28:Radix sort, tries.
   09/29: (recitation) B-trees & treaps review. Adding auxiliary info to data structures.
10. 09/30:Hashing.
    
11. 10/05:Dynamic Programming.
    10/06: (recitation) Search trees vs hashing; another method for universal hashing.
    
12. 10/07:DP contd; Graph Algorithms I: DFS and Topological Sorting.
    
13. 10/12:Graph Algorithms II: shortest path, bottleneck path, Bellman-Ford.
    10/13: (recitation) All-pairs shortest paths: Matrix products, Floyd-Warshall.
    
14. 10/14:Graph Algorithms III: Minimum spnning trees (Prim, Kruskal). Union-find.
    
15. 10/21:Network Flows and Matchings I.
    
16. 10/26:Network Flows and Matchings II.
    
17. 10/28:Linear Programming.
    
18. 11/02:NP-completeness I.
    
19. 11/04:NP-completeness II.
    
20. 11/09:NP-completeness III.
    11/10: (recitation) Circuit-SAT and 3-SAT..
    
21. 11/11:Approximation Algorithms.
    
22. 11/16:Online Algorithms.
    
23. 11/18:Number theoretic algorithms I.
    
24. 11/23:Number theoretic algorithms II.
    
25. 11/30:Fast Fourier Transform (FFT).
    12/01: (recitation) More on Number Theory and FFT..
    
26. 12/02:Fair division: fair and envy-free cake-cutting.
    
27. 12/07:Intro to game theory.
    
28. 12/09:Learning Finite-State Environments.