No. | Date | Topics | Readings | Homework |
1 | 01/10 M | Introduction, Algorithm, Complexity, Various Equalities, Graphs, Recursion Tree, Master Theorem, Akra-Bazzi Theorem, Divide and Conquer (Strassen, Binary Multiplication), Dynamic Programming, Breadth First Search, Topological Sort, Minimum Spanning Trees, Shortest Paths | [Kozen 1] [CLR 1, 2, 3, 4, 5.4] | Homework 0 (PS) Solution (PS) |
2 | 01/12 W | Hints, Depth First Search, Strongly Connected Components | [Kozen 2, 4, 5] [CLR 23, 24, 25] | |
3 | 01/14 F | More strongly connected components, minimum spanning forest | [Kozen 4] [CLR 23, 24] | |
4 | 01/17 M | (Martin Luther King Day) NO CLASS | | |
5 | 01/19 W | Union-Find, Analysis | [Kozen 10,11] [CLR 22] | Homework 0 Due. Homework 1 (PS) Solution (PS) |
6 | 01/21 F | Heaps, Binomial Heaps, Amortized Analysis of Binomial Heaps | [Kozen 8] [CLR 20] | |
7 | 01/24 M | Fibonacci Heaps | [Kozen 9] [CLR 21] | |
8 | 01/26 W | More Fibonacci Heaps | [Kozen 9] [CLR 21] | |
9 | 01/28 F | Treaps (Random Search Trees) | [Kozen 13] [M&R 8.2] | Homework 1 Due. Homework 2 (PS) Q1 picture Solution |
10 | 01/31 M | More Treaps | [Kozen 13] | |
11 | 02/02 W | Splay Trees | [Kozen 12] Sleator's note | |
12 | 02/04 F | Splay Trees Proof | [Kozen 12] | Practice Midterm Solution |
13 | 02/07 M | No class | | |
14 | 02/09 W | Midterm 1 -- Part 1 | | |
15 | 02/11 F | Midterm 1 -- Part 2 | | |
16 | 02/14 M | Planar Graphs, 5-coloring | | |
17 | 02/16 W | Planarity Testing | [Kozen 14] | |
18 | 02/18 F | Planar Separator Theorem 1 | [Kozen 15] | |
19 | 02/21 M | Subhash Khot's Talk (Attendence not required) | | |
20 | 02/23 W | Planar Separator Theorem 2 | [Kozen 15] | Homework 3 (PS) Solution |
21 | 02/25 F | Planar Separators | [Kozen 15] | |
22 | 02/28 M | NP-Completeness 1 (Introduction) | [Kozen 21, 22, 23, 24] [CLR 36] | |
23 | 03/02 W | NP-Completeness 2 (Random NP Problems) | [Kozen 21, 22, 23, 24] [CLR 36] | |
24 | 03/04 F | Mid-Semester Break; No Class | | |
| 03/07 M | ----------------- (Spring Break) | | |
| 03/09 W | ----------------- (Spring Break) | | |
| 03/11 F | ----------------- (Spring Break) | | |
25 | 03/14 M | NP-Completeness 3 (NP, co-NP, NP-hard, Independent Set) | [Kozen 21, 22, 23, 24] [CLR 36] | |
26 | 03/16 W | NP-Completeness 4 (Independent Set and Cook's Theorem) | [Kozen 21, 22, 23, 24] [CLR 36] | |
27 | 03/18 F | NP-Completeness 5 (Cook's Theorem) | [Kozen 21, 22, 23, 24] [CLR 36] | |
28 | 03/21 M | NP-Completeness 6 (Hamiltonian Cycle to SAT) | [Kozen 21, 22, 23, 24] [CLR 36] | |
29 | 03/23 W | Guest Lecturer: Anupam Gupta on Approximation Algorithms | [CLR 37] | Homework 4 (PS) Solution (PS)
|
30 | 03/25 F | Randomized 2-SAT | | |
31 | 03/28 M | Polynomial identity checking | [Kozen 40] [M&R 7.2] | |
32 | 03/30 W | Polynomial identity checking | [Kozen 40] [M&R 7.2] | |
33 | 04/01 F | Midterm 2 | | |
34 | 04/04 M | Matching | [Kozen 19, 20] [M&R 7.3] | |
35 | 04/06 W | RP, Randomized Algorithms -- Test of Associativity | | |
36 | 04/08 F | RP, Randomized Algorithms | | |
37 | 04/11 M | Random Walks -- 1, 2, and 3 dimensions | [M&R 6] | |
38 | 04/13 W | String and Set Equality | | |
39 | 04/15 F | No class (Spring Carnival) | | Homework 5 (PS) Solution |
40 | 04/18 M | Random Walks on General Graph | [M&R 6] | |
41 | 04/20 W | How to Write a Proof | | |
42 | 04/22 F | The probabilistic method - Max-Cut; Randomized and Deterministic 1/2-Approximation Algorithms for Max-Cut | [M&R 5.1] | |
43 | 04/25 M | Final Review by Chris and Virginia | | |
45 | 04/27 W | Free Cake: Cake Cutting | | |
44 | 04/29 F | "Sunny" Day, No Class | | |
46 | 05/05 Thursday | Final Exam. 8:30a.m. to 11:30a.m. DH 2302 | | |