CMU 15-451 (Algorithms), Fall 2004
TAs: Doru Balcan, Nina Balcan, Jon Derryberry,
- Our final exam is Fri Dec 17, 1-4pm, and will be in DH 2210.
One sheet of notes allowed (but closed-book).
- For practice, here is last year's final.
Here are solutions.
- Graded homework #7's are in the course secretary's office, Wean 4116.
- Here are solutions to
We will be using the textbook "Introduction to Algorithms (Second
Edition)" by Cormen, Leiserson, Rivest, and Stein.
- Course information
- The course bboards are: academic.cs.15-451 (for announcements)
and academic.cs.15-451.discuss (for general discussion).
- Mini 1. Due midnight Sept
- Mini 2. Due midnight Sept
- Mini 3. Due midnight Oct
- Mini 4. Due midnight Nov
- Mini 5 [ps, pdf]. Due midnight Dec 2.
- Homework 1 [ps, pdf]. Due (in class) Sept 14.
- Homework 2 [ps, pdf]. Due Sept 28/29 (oral
- Homework 3 [ps, pdf]. Due (in class) Oct 12.
- Homework 4 [ps, pdf]. Due Oct 26/27 (oral
- Homework 5 [ps, pdf]. Due (in class) Nov 9.
- Homework 6 [ps, pdf]. Due Nov 22/23 (oral
- Homework 7 [ps, pdf]. Due (in class) Dec 9.
- 08/31:Intro & Admin.
09/01: (recitation) Warmup problems.
- 09/02:Asymptotic analysis,
- 09/07:Probabilistic analysis,
09/08: (recitation) Insertion sort and inversions.
- 09/09:Linear-time Selection
(randomized and deterministic).
- 09/14:Upper and lower bounds
in simplified models of computation.
09/15: (recitation) Review + Coupon collector's problem.
- 09/16:Upper and lower bounds
- 09/21:Amortized Analysis
09/22: (recitation) Amortized analysis + Practice Quiz.
- 09/23:Search trees: B-trees and treaps.
- 09/28:Radix sort, tries.
09/29: (recitation) B-trees & treaps
review. Adding auxiliary info to data structures.
- 10/05:Dynamic Programming.
Search trees vs hashing; another method for universal hashing.
- 10/07:DP contd; Graph Algorithms I: DFS and Topological Sorting.
- 10/12:Graph Algorithms II:
shortest path, bottleneck path, Bellman-Ford.
10/13: (recitation) All-pairs
shortest paths: Matrix products, Floyd-Warshall.
- 10/14:Graph Algorithms III:
Minimum spnning trees (Prim, Kruskal). Union-find.
- 10/21:Network Flows and Matchings I.
- 10/26:Network Flows and Matchings II.
- 10/28:Linear Programming.
- 11/02:NP-completeness I.
- 11/04:NP-completeness II.
- 11/09:NP-completeness III.
11/10: (recitation) Circuit-SAT and 3-SAT..
- 11/11:Approximation Algorithms.
- 11/16:Online Algorithms.
- 11/18:Number theoretic algorithms I.
- 11/23:Number theoretic algorithms II.
- 11/30:Fast Fourier Transform (FFT).
12/01: (recitation) More on Number Theory and FFT..
- 12/02:Fair division: fair and
- 12/07:Intro to game theory.
- 12/09:Learning Finite-State Environments.