# CMU 15-451 (Algorithms), Fall 2000

### TAs: Mike Bowling, Nick Hopper, Dan Tennant

**Heads-up:** The Final is on
Monday Dec 18, 8:30am-11:30am in PH100. You may use 1 sheet of
notes (but the final is not open book).
Last year's final is available below.

### Course information

### Assignments

### Other Handouts and Practice problems

### Lecture Notes

Here are some lecture notes for your convenience. Please feel free
to email the instructor if you notice any mistakes in them. We
are providing these for any students interested.

- 08/29:Intro & Admin.
Karatsuba multiplication.
- 08/31:Asymptotic analysis. Solving
recurrences.
- 09/05:Probabilistic analysis. Randomized Quicksort.
- 09/07:Linear-time selection (randomized
and deterministic).
- 09/12:Lower bounds for comparison
sorting.
- 09/14:Balanced search trees I: B-trees.
- 09/19:Amortized analysis.
- 09/21:Splay Trees.
- 09/26:Tries and Radix Sort.
- 09/28:Hashing I: basics + universal hashing.
- 10/03:Hashing II: universal and
perfect hashing.
- 10/05:Dynamic Programming.
- 10/10:Graph Algorithms I.
- 10/12:Binomial and Fibonacci
heaps.
- 10/17:Midterm.
- 10/19:Graph algs II: Dijkstra, Prim, Kruskal.
- 10/24:Union-find.
- 10/26:Network flow and bipartite matching.
- 10/31:Network flow, contd: more
examples + Edmonds-Karp.
- 11/02:Linear Programming.
- 11/07:NP-Completeness.
- 11/09:NP-Completeness, contd.
- 11/14:DFT and FFT (postscript).
- 11/16:Number-theoretic algs I.
- 11/21:Number-theoretic algs II.
- 11/28:Approximation algorithms.
- 11/30:Zero Knowledge (postscript).
- 12/05:Competitive Algorithms: text
and slides (PDF)
- 12/07:Online machine learning.
- 12/12:Summary.

*Avrim Blum* avrim+@cs.cmu.edu