- Lectures: Tue/Thu 12-1:20, GHC 4401.
- Recitations:
- A: Wed 10:30 (WEH 4709) - Wendy Hu
- B: Wed 11:30 (WEH 4709) - Zak Wise
- C: Wed 9:30 (WEH 4709) - Wendy Hu
- D: Wed 2:30 (WEH 4709) - Aditya Prakash
- E: Wed 3:30 (WEH 4709) - Nate Barshay

- Course information (including email and office hour info)
- Schedule (including test dates)

- Mini 1. Due 11:59pm Sept 6.
- Mini 2. Due 11:59pm Sept 20.
- Mini 3. Due 11:59pm Oct 4.
- Mini 4. Due 11:59pm Nov 1.
- Mini 5. Due 11:59pm Dec 1.

- Homework 1 [pdf][tex]. Solutions.
- Homework 2 [pdf]. Presentations Sept 27-29.
- Homework 3 [pdf][tex]. Solutions.
- Homework 4 [pdf]. Solutions.
- Homework 5 [pdf][tex]. Solutions.
- Homework 6 [pdf]. Presentations Nov 21-22.
- Homework 7 [pdf][tex]. Solutions.

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

08/31: (recitation) Warmup problems.

- 09/01:Asymptotic analysis, solving recurrences.

- 09/06:Probabilistic analysis, Randomized Quicksort.

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

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

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

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

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

- 09/20: Tight upper/lower bounds for matrix searching

09/21: (recitation) radix sort

- 09/22:Amortized Analysis

- 09/27:Search trees: B-trees
and treaps

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

- 09/29: Result-checking: programs that check their work.
- 10/04:Universal and Perfect Hashing.

10/05: (recitation) universal hashing recap, alternative hashing scheme, cryptographic hash functions, testing matrix multiplication.

- 10/06:Dynamic Programming.

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

10/12: (recitation) Discuss practice midterm. - 10/13:Graph Algorithms II:
Dijkstra, Prim, Kruskal.

- 10/20:Graph Algorithms III:
Union-find and planarity testing (notes cover only
union-find).

P.S. here is the original Hopcroft-Tarjan planarity-testing paper. (note the need to define O() and the basic model of computation in the intro. The key idea for the algorithm is given in section 4).

- 10/25:Network Flows and Matchings I.

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

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

- 11/01:Linear Programming.

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

- 11/03:NP-completeness I.

- 11/08:NP-completeness II.

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

- 11/10: Beyond NP-completeness (see notes above, plus material we
won't test on PSPACE, Savitch's theorem, alternation)

- 11/15:Approximation Algorithms.

- 11/17:Online Algorithms.

- 11/22:Number theoretic algorithms I: Pollard's rho algorithm.

- 11/29:Number theoretic
algorithms II: Lattice basis reduction. [LLL paper]

11/30: (recitation) Number theory basics, Extended GCD, inverses, Fermat's little thm, Euler's them.

- 12/01:Fast Fourier Transform (FFT).

- 12/06:Intro to game theory.

12/07: (recitation) Course recap.

- 12/08:Intro to machine learning theory.