CMU 15-451 (Algorithms), Fall 2006
TAs: Hubert Chan, Varun Gupta, Srinath Sridhar, and
Matus Telgarsky
Reminder:
The final exam is scheduled for Fri Dec 15, 8:30-11:30am in PH100 (1
sheet of notes allowed). We
will have a review session Wed Dec 13, 1:30-3:00, in Wean 7500.
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 2105).
- 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 5.
- Mini 2. Due midnight Sept 19.
- Mini 3. Due midnight Oct 3.
- Mini 4. Due midnight Oct 31.
- Mini 5 [ps,
pdf]. Due midnight Nov 30.
Homeworks
- Homework 1 [ps, pdf]. Due (start of class) Sept 12.
Solutions [ps,
pdf].
- Homework 2 [ps, pdf]. Due Sept 26/27 (oral
presentations).
Solutions [ps, pdf].
- Homework 3 [ps, pdf]. Due (start of class) Oct 10.
Solutions [ps, pdf].
- Homework 4 [ps, pdf]. Due Oct 24/25 (oral presentations).
Solutions [ps, pdf].
- Homework 5 [ps, pdf]. Due (start of class) Nov 7.
Solutions [ps,pdf]
- Homework 6 [ps, pdf]. Due Nov 20/21 (oral presentations).
Solutions [ps, pdf].
- Homework 7 [ps, pdf]. Due (start of class) Dec 7. (more copies available outside Wean 4116)
Lecture notes (in pdf and txt)
- 08/29:Intro & Admin. Karatsuba/Strassen. [The first 10 lectures]
08/30: (recitation) Warmup problems.
- 08/31:Asymptotic analysis, solving recurrences.
- 09/05:Probabilistic analysis, Randomized Quicksort.
09/06: (recitation) Problems related
to randomized quicksort, insertion sort.
- 09/07:Linear-time Selection
(randomized and deterministic).
- 09/12:Lower bounds for
comparison-based sorting.
- 09/14:Concrete models of
computation and tight upper/lower bounds
- 09/19:Amortized Analysis
09/20: (recitation) Amortized
analysis + Go over practice quiz.
- 09/21:Search trees: B-trees
and treaps.
- 09/26:Digit-based
sorting/data-structures (radix sort, tries).
- 09/28:Universal and Perfect Hashing.
- 10/03:Dynamic Programming.
- 10/05:Graph Algorithms I: DFS
and Topological Sorting, DP algs for
shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
- 10/10:Graph Algorithms II:
Dijkstra, Prim, Kruskal.
- 10/12:Bottleneck paths, MSTs,
union-find, and Midterm review.
- 10/19:Graph Algorithms III:
coloring, strongly-connected components.
- 10/24:Fair division: fair and
envy-free cake-cutting.
- 10/26:Network Flows and Matchings I.
- 10/31:Network Flows II:
Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
- 11/02:Linear Programming.
- 11/07:NP-completeness I.
- 11/09:NP-completeness II.
- 11/14:Approximation Algorithms.
- 11/16:Online Algorithms.
- 11/21:Number theoretic algorithms I.
- 11/28:Number theoretic algorithms II.
- 11/30:Fast Fourier Transform (FFT).
- 12/05:Intro to game theory.
- 12/07:Learning Finite-State Environments.