CMU 15-451 (Algorithms), Fall 2001

Instructors: Avrim Blum, Klaus Sutner

TAs: Yan Karklin, Sam Pinansky, Weng-Keen Wong

For the official course webpage, go to http://www.cmu.edu/blackboard

Course information

Assignments

Homework 1. Solutions.
Homework 2. Solutions.
Homework 3. Solutions.
Homework 4. Solutions.
Homework 5. Solutions.
Correction: You should assume for 3(b) that the option MUST be exercised EXACTLY at time T. (As opposed to exercising it any time between now and T, as in 3(a)).
Homework 6. Solutions.
Homework 7. Solutions.

Lecture notes

08/28:Intro & Admin. Karatsuba multiplication.
Recitation 08/29: sample problems
08/30:Asymptotic analysis. Solving recurrences.
09/04:Probabilistic analysis. Randomized Quicksort.
Recitation 09/05: recurrence, probability examples
09/06:Linear-time selection (randomized and deterministic).
09/11:Lower bounds for comparison sorting.
Recitation 09/12:coupon-collector, coin-flipping, and H_n
09/13:Dynamic programming.
09/18:Balanced search trees.
Recitation 09/19: quiz review.
09/20:Amortized analysis.
09/25:Self-adjusting lists and trees. Here are some additional notes.
09/27:Radix structures.
10/02:Hashing I.
10/04:Hashing II.
10/09:Graph algs I: topological sort, MST (Prim and Kruskal).
10/11:Union-find.
10/16:Graph exploration and matrix-based graph algorithms.
10/23:Strongly connected components & related algorithms.
10/25:Network Flows and Matchings I (Ford-Fulkerson, Edmonds-Karp #1).
10/30:Network Flows and Matchings II (Edmonds-Karp #2, Dinic/MPM, Min-cost Max-flow).
11/01:Linear Programming.
11/06:NP-completeness I.
11/08:NP-completeness II.
11/13:Approximation Algorithms.
11/15:Number-theoretic algorithms I.
11/20:Number-theoretic algorithms II.
11/27:The Fast Fourier Transform.
11/30:Minimizing Finite Automata.
12/04:Shortest paths, Global minimum cuts.
12/06:String matching.
12/11:Review & further directions.