Note:Final is closed book, 1 sheet of notes. Final will be in GHC 4401, Fri Dec 11 8:30-11:30am. Good luck!

- Lectures: Tue/Thu 12-1:20, GHC 4401.
- Recitations:
- A: Wed 10:30 (BH 136A) - Zizhuang Yang
- B: Wed 11:30 (GHC 4215) - Sameer Chopra
- C: Wed 9:30 (HBH 1002) - Vicki Cheung
- D: Wed 2:30 (WEH 4623) - Khalid El-Arini
- E: Wed 3:30 (GHC 4211) - Jiri Simsa

- Course information
- Schedule
- How to sign up for the course bboards

- Mini 1. Due midnight Sept 1.
- Mini 2. Due midnight Sept 15.
- Mini 3. Due midnight Oct 1.
- Mini 4. Due midnight Oct 27.
- Mini 5. Due midnight Nov 24..

- 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: hardcopy available outside GHC 8120. [pdf w/o attached practice test]. Due Dec 3.

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

08/26: (recitation) Warmup problems.

- 08/27:Asymptotic analysis, solving recurrences.

- 09/01:Probabilistic analysis, Randomized Quicksort.

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

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

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

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

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

- 09/15:Amortized Analysis

09/16: (recitation) problems related to tight bounds and minimax optimality.

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

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

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

- 09/29:Universal and Perfect Hashing.

09/30: (recitation) Go over quiz, universal hashing recap, alternative universal hashing scheme.

- 10/01:Dynamic Programming.

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

10/07: (recitation) matrix method and Floyd-Warshall.

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

- 10/13: Midterm.

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

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

- 10/20:Network Flows and Matchings I.

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

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

- 10/27:Linear Programming.

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

- 10/29:NP-completeness I.

- 11/03:NP-completeness II.

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

- 11/05:Approximation Algorithms.

- 11/10:Online Algorithms.

11/11: (recitation) More NP-completeness and approx algs: Set-Splitting and MAX-Exactly-3-SAT.

- 11/12:Number theoretic algorithms I.

- 11/17:Number theoretic algorithms II.

11/18: (recitation) Number theory and more interesting complexity classes.

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

- 11/24:Intro to game theory.

- 12/01:Intro to machine learning theory.

12/02: (recitation) FFT for string matching, general course review.

- 12/03:Mechanism/protocol design,
cake cutting.