CMU 15-451 (Algorithms), Fall 2007
TAs: Michael Dinitz, Jiquan Ngiam, Aaron Roth, Samuel Wang
General info
- Lectures: Tue/Thu 12-1:20, Wean 7500.
- Recitations: Wed 12:30/1:30/2:30/12:30. (A,B,C in SH219; D in DH2105)
- Course information
- Schedule
- The course bboards are: academic.cs.15-451 (for announcements)
and academic.cs.15-451.discuss (for general discussion).
Minis
Homeworks
- Homework 1 [ps, pdf]. Due (start of class) Sept 11.
Solutions [ps,
pdf].
- Homework 2 [ps, pdf]. Due Sept 25/26 (oral
presentations).
Solutions [ps, pdf].
- Homework 3 [ps, pdf]. Due (start of class) Oct 9.
Solutions [ps, pdf].
- Homework 4 [ps, pdf]. Due Oct 23/24 (oral presentations).
Solutions [ps, pdf].
- Homework 5 [ps, pdf]. Due (start of class) Nov 6.
Solutions [ps,pdf]
- Homework 6 [ps, pdf]. Due Nov 19/20 (oral presentations).
Solutions [ps, pdf].
- Homework 7 [ps, pdf]. Due (start of class) Dec 6. Solutions [ps, pdf].
- 08/28:Intro & Admin. Karatsuba/Strassen.
08/29: (recitation) Warmup problems.
- 08/30:Asymptotic analysis, solving recurrences.
- 09/04:Probabilistic analysis, Randomized Quicksort.
09/05: (recitation) Problems related
to randomized quicksort, insertion sort.
- 09/06:Linear-time Selection
(randomized and deterministic).
- 09/11:Concrete models and tight
upper/lower bounds I.
09/12: (recitation) Problems related
to selection recurrence, getting
upper/lower bounds in concrete models.
- 09/13:Optional review: hwk1,
probability practice, coupon collector's problem.
[more details]
- 09/18:Concrete models
and tight upper/lower bounds II
09/19: (recitation) Problems related
to tight bounds, connection to minimax optimality in games.
- 09/20:Amortized Analysis
- 09/25:Search trees: B-trees
and treaps.
09/26: (recitation) B-tree
example + go over practice quiz.
- 09/27:Universal and Perfect Hashing.
- 10/02:Digit-based
sorting/data-structures (radix sort, tries).
- 10/04:Dynamic Programming.
- 10/09:Graph Algorithms I: DFS
and Topological Sorting, DP algs for
shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
- 10/11:Graph Algorithms II:
Dijkstra, Prim, Kruskal.
- 10/16:Graph Algorithms III: Union-find.
- 10/23:Network Flows and Matchings I.
10/24: (recitation) Examples of
problems that can be solved using network flow.
- 10/25:Network Flows II:
Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
- 10/30:Linear Programming.
10/31: (recitation) Examples of
problems that can be solved using linear programming.
- 11/01:NP-completeness I.
- 11/06:NP-completeness II.
11/07: (recitation) Examples of
NP-completeness reductions: Integer Programming and 3-Coloring.
- 11/08:Approximation Algorithms.
- 11/13:Online Algorithms.
- 11/15:Number theoretic algorithms I.
- 11/20:Number theoretic algorithms II.
- 11/27:Fast Fourier Transform (FFT).
- 11/29:Intro to machine learning theory.
- 12/04:Intro to game theory.
- 12/06:Fair division: fair and
envy-free cake-cutting.