| Date | Topics | Readings | Homework | |
| 01/10 M | Introduction | [Kozen 1] [CLRS 1, 2, 3, 4, 5.4] [ Computational Complexity: A Modern Approach(optional)] | Hwk 0 (Sol) | |
| 01/12 W | Heaps, Binomial Heaps | [Kozen 8] [CLRS 20] | ||
| 01/14 F | Fibonacci Heaps | [Kozen 9] [CLRS 19] | ||
| 01/17 M | (Martin Luther King Day)NO CLASS | |||
| 01/19 W | More Fibonacci Heaps | [Kozen 9] [CLRS 19] | ||
| 01/21 F | Union-Find | [Kozen 10,11] [CLRS 21] | Hwk 1 (Sol) | |
| 01/24 M | More Union-Find | [Kozen 10,11] [CLRS 21] | ||
| 01/26 W | Splay Trees | [Kozen 12] Sleator's notes , Sleator's notes (cont.) | ||
| 01/28 F | --- | |||
| 01/31 M | More Splay Trees | |||
| 02/02 W | Treaps (Random Search Trees) | [Kozen 13] [M&R 8.2] | [Kozen 13] [M&R 8.2] | |
| 02/04 F | Discussion on randomized algorithms | Hwk 2 (Sol) | ||
| 02/07 M | Graph Planarity | [Kozen 14] | ||
| 02/09 W | Planarity Testing | Hopcroft-Tarjan Efficient Planarity testing | ||
| 02/11 F | General discussion | |||
| 02/14 M | Planar Separator Theorem 1 | [Kozen 15] | ||
| 02/16 W | Planar Separator Theorem 2 | [Kozen 15] | ||
| 02/18 F | Planar Separator Theorem 3 | [Kozen 15] | ||
| 02/21 M | Planar Separator Theorem 4 | |||
| 02/23 W | Randomizing Algorithms 1 | [Kozen 40] Schwartz's paper | ||
| 02/25 F | CSD Open House NO CLASS | Hwk 2 due | ||
| 02/28 M | Randomizing Algorithms 2 | Schwartz's Lemma over GF(p); A problem in communication complexity | Hwk 3 out | |
| 03/02 W | Randomizing Algorithms 3 | [ Lovasz's Survey on random walks] [M&R 6] | ||
| 03/04 F | (Mid-Semester Break) NO CLASS | |||
| 03/07 M | (Spring Break) NO CLASS | |||
| 03/09 W | (Spring Break) NO CLASS | |||
| 03/11 F | (Spring Break) NO CLASS | |||
| 03/14 M | Review | [Practice Midterm 1 (solutions)] [Practice Midterm 2 (solutions)] | ||
| 03/16 W | Midterm | |||
| 03/18 F | Harsha: Parallel Algorithms (Programming models, Work and Depth, Brent's theorem, Prefix-sum) | [Blelloch: Ch. 1 (Synthesis of Parallel Algorithms)] Bob Harper: Parallelism and Concurrency, Languages and Machines Guy Blelloch: Programming Parallel Languages Lecture notes for 3/28, 3/21. Scribe: Ilari | ||
| 03/21 M | Harsha: Parallel Algorithms (Prefix-sum, List-ranking) | Synthesis of Parallel Algorithms: Chap 2, Chap 3 Lecture notes for 3/28, 3/21. Scribe: Ilari | Hwk 3 due | |
| 03/23 W | Introduction to the class NP | [Kozen 21, 22, 23, 24] [CLRS 36][Garey & Johnson] | ||
| 03/25 F | Decision and Search problems | [Kozen 21, 22, 23, 24] [CLRS 36][Garey & Johnson] | Hwk 4 out | |
| 03/28 M | Harsha: Parallel Algorithms (More List-ranking) | Lecture notes, Scribe: Sriram Somanchi Synthesis of Parallel Algorithms: Chap 2, Chap 3 | ||
| 03/30 W | Definition of the class NP | [Kozen 21, 22, 23, 24] [CLRS 36][Garey & Johnson] | ||
| 04/01 F | NP-Completeness 1 | |||
| 04/04 M | NP-Completeness 2 | Hwk 5 out Hwk 4 due | ||
| 04/06 W | NP-Completeness 3 | |||
| 04/08 F | NP-Hard problems 1 | |||
| 04/11 M | NP-Hard problems 2 | |||
| 04/13 W | NP-Hard problems 3 | |||
| 04/15 F | (Spring Carnival) NO CLASS | |||
| 04/18 M | Integer Linear Programs | Hwk 5 due | ||
| 04/20 W | Liu Yang: Online Learning Mistake Bound Model | [Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm][ Survery article: Avrim Blum, On-Line Algoriothms in Machine Learning] | ||
| 04/22 F | Anupam Gupta: Approximation Algorithms 1 | 15-854: CMU course on approximation algorithms with lecture notes | Hwk 6 out | |
| 04/25 M | Levin's Algorithm (for factoring) | |||
| 04/27 W | Open problems: Graph isomorphim, Circuit Value problem with MIN,MAX,AVG gates | |||
| 04/29 F | Anupam Gupta: Online algorithms (Ski rental problem, k-server problem) | k-server problems: Notes 1 Notes 2 | ||
| 05/03 T | Final Exam, at 6.00PM, Gates 6115 | Practice final 1 , Practice final 2 , Practice Problem Set 1 |