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

- 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 7.
- Mini 2. Due midnight Sept 21.
- Mini 3. Due midnight Oct 5.
- Mini 4. Due midnight Nov 2.
- Mini 5 [ps, pdf]. Due midnight Dec 2.

- Homework 1 [ps, pdf]. Due (in class) Sept 14. Solutions [ps, pdf].
- Homework 2 [ps, pdf]. Due Sept 28/29 (oral presentations). Solutions [ps, pdf].
- Homework 3 [ps, pdf]. Due (in class) Oct 12. Solutions [ps, pdf].
- Homework 4 [ps, pdf]. Due Oct 26/27 (oral presentations). Solutions [ps, pdf].
- Homework 5 [ps, pdf]. Due (in class) Nov 9. Solutions [ps]
- Homework 6 [ps, pdf]. Due Nov 22/23 (oral presentations). Solutions [ps, pdf].
- Homework 7 [ps, pdf]. Due (in class) Dec 9. Solutions [ps, pdf].

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

09/01: (recitation) Warmup problems.

- 09/02:Asymptotic analysis,
solving recurrences.

- 09/07:Probabilistic analysis,
Randomized Quicksort.

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/16:Upper and lower bounds
(II)

- 09/21:Amortized Analysis
- 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. - 09/30:Hashing.

- 10/05:Dynamic Programming.

10/06: (recitation) 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
envy-free cake-cutting.

- 12/07:Intro to game theory.

- 12/09:Learning Finite-State Environments.