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 |