- Lectures: Tue/Thu 12-1:20, Wean 7500.
- Recitations:
- A: Wed 12:30, SH 208 (TA: Sameer Chopra)
- B: Wed 1:30, WeH 5312 (TAs: Daegun Won and Jim Spagnola)
- C: Wed 2:30, SH 219 (TA: Jenn Tam)
- D: Wed 12:30, CFA 211 (TA: Matt Delaney)

- 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 2.
- Mini 2. Due midnight Sept 16.
- Mini 3. Due midnight Sept 30.
- Mini 4. Due midnight Oct 28.
- Mini 5. Due midnight Nov 25.

- Homework 1 [ps, pdf]. Solutions [ps, pdf].
- Homework 2 [ps, pdf]. Solutions [ps, pdf].
- Homework 3 [ps, pdf]. Solutions [ps, pdf].
- Homework 4 [ps, pdf]. Solutions [ps, pdf].
- Homework 5 [ps, pdf]. Solutions [ps, pdf].
- Homework 6 [ps, pdf]. Solutions [ps, pdf].
- Homework 7 [ps, pdf]. Solutions [ps, pdf].

- 08/26:Intro & Admin. Karatsuba/Strassen.

08/27: (recitation) Warmup problems.

- 08/28:Asymptotic analysis, solving recurrences.

- 09/02:Probabilistic analysis, Randomized Quicksort.

09/03: (recitation) Problems related to randomized quicksort, insertion sort.

- 09/04:Linear-time Selection
(randomized and deterministic).

- 09/09:Comparison-based lower
bounds for sorting.

09/10: (recitation) Problems related to selection recurrence, upper/lower bounds in concrete models.

- 09/11:Concrete models
and tight upper/lower bounds

- 09/16:Amortized Analysis

09/17: (recitation) Common problems in hwk1, problems related to tight bounds and minimax optimality.

- 09/18:Search trees: B-trees
and treaps.

- 09/23:Digit-based
sorting/data-structures (radix sort, tries).

09/24: (recitation) B-tree and treap examples, treap analysis.

- 09/25:Universal and Perfect Hashing.

- 09/30:Dynamic Programming.

10/01: (recitation) Hashing and DP review.

- 10/02:Graph Algorithms I: DFS
and Topological Sorting, DP algs for
shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).

- 10/07:Graph Algorithms II:
Dijkstra, Prim, Kruskal.

10/08: (recitation) Maximum bottleneck path, coupon-collector's problem.

- 10/09: review.

10/15: (recitation) 2-coloring, BFS and DFS trees.

- 10/16:Graph Algorithms III: Union-find.

- 10/21:Network Flows and Matchings I.

10/22: (recitation) Examples of problems that can be solved using network flow.

- 10/23:Network Flows II:
Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.

- 10/28:Linear Programming.

10/29: (recitation) Examples of problems that can be solved using linear programming.

- 10/30:NP-completeness I.

11/04: - no class today -

11/05: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.

- 11/06:NP-completeness II.

- 11/11:Approximation Algorithms.

- 11/13:Online Algorithms.

- 11/18:Number theoretic algorithms
I.

11/19: (recitation) More NP-completeness and number theory.

- 11/20:Number theoretic algorithms II.

- 11/24:Fast Fourier Transform (FFT).

- 12/02:Intro to machine learning theory.

- 12/04:Intro to game theory.