CMU 15-451 (Algorithms), Fall 2011
TAs: Nathaniel Barshay, Wendy Hu, B. Aditya
Prakash, Zak Wise, and Lidong Zhou
General info
- Lectures: Tue/Thu 12-1:20, GHC 4401.
- Recitations:
- A: Wed 10:30 (WEH 4709) - Wendy Hu
- B: Wed 11:30 (WEH 4709) - Zak Wise
- C: Wed 9:30 (WEH 4709) - Wendy Hu
- D: Wed 2:30 (WEH 4709) - Aditya Prakash
- E: Wed 3:30 (WEH 4709) - Nate Barshay
- Course information (including email
and office hour info)
- Schedule (including test dates)
Minis
Homeworks
- 08/30:Intro & Admin. Karatsuba/Strassen.
08/31: (recitation) Warmup problems.
- 09/01:Asymptotic analysis, solving recurrences.
- 09/06:Probabilistic analysis, Randomized Quicksort.
09/07: (recitation) Problems related
to randomized quicksort, insertion sort.
- 09/08:Linear-time Selection
(randomized and deterministic).
- 09/13:Comparison-based lower
bounds for sorting.
09/14: (recitation) Problems related
to selection recurrence, upper/lower bounds in concrete models.
- 09/15:Concrete models
and tight upper/lower bounds
- 09/20: Tight upper/lower bounds for matrix searching
09/21: (recitation) radix sort
- 09/22:Amortized Analysis
- 09/27:Search trees: B-trees
and treaps
09/28: (recitation) B-tree
and treap examples, treap analysis.
- 09/29: Result-checking: programs that check their work.
- 10/04:Universal and Perfect Hashing.
10/05: (recitation)
universal hashing recap, alternative hashing scheme,
cryptographic hash functions, testing matrix multiplication.
- 10/06:Dynamic Programming.
- 10/11:Graph Algorithms I: DFS
and Topological Sorting, DP algs for
shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
10/12: (recitation) Discuss practice midterm.
- 10/13:Graph Algorithms II:
Dijkstra, Prim, Kruskal.
- 10/20:Graph Algorithms III:
Union-find and planarity testing (notes cover only
union-find).
P.S. here is the original Hopcroft-Tarjan planarity-testing paper. (note the need to define O() and the basic model of computation in the intro. The key idea for the algorithm is given in section 4).
- 10/25:Network Flows and Matchings I.
10/26: (recitation) Examples of
problems that can be solved using network flow.
- 10/27:Network Flows II:
Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
- 11/01:Linear Programming.
11/02: (recitation) Examples of
problems that can be solved using linear programming.
- 11/03:NP-completeness I.
- 11/08:NP-completeness II.
11/09: (recitation) Examples of
NP-completeness reductions: Integer Programming and 3-Coloring.
- 11/10: Beyond NP-completeness (see notes above, plus material we
won't test on PSPACE, Savitch's theorem, alternation)
- 11/15:Approximation Algorithms.
- 11/17:Online Algorithms.
- 11/22:Number theoretic algorithms I: Pollard's rho algorithm.
- 11/29:Number theoretic
algorithms II: Lattice basis reduction. [LLL paper]
11/30: (recitation) Number
theory basics, Extended GCD, inverses, Fermat's little thm, Euler's them.
- 12/01:Fast Fourier Transform (FFT).
- 12/06:Intro to game theory.
12/07: (recitation) Course recap.
- 12/08:Intro to machine learning theory.