- 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).

- Mini 1. Due midnight Sept 4.
- Mini 2. Due midnight Sept 18.
- Mini 3. Due midnight Oct 2.
- Mini 4. Due midnight Oct 30.
- Mini 5. Due midnight Nov 29.

- 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.