| Date |
Topics |
Reading |
| Tue, August 23 |
Intro, administrivia, complexity classes P, NP, EXP, PSPACE |
Chapter 8 of Dasgupta etal, notes of Jeff, Sariel, Chandra on NP-Completeness |
| Thu, August 25 |
Poly-time reductions, NP-Completeness |
Same as for previous lecture |
| Tue, August 30 |
Finish NP-Completeness |
3DM to Subset Sum is from Kleinberg-Tardos |
| Thu, Sept 1 |
Recursion, Divide and Conquer, Linear time Selection, Randomization |
Chapter 2 of Dasgupta etal. Notes of Jeff/Sariel/Chandra |
| Tue, Sept 6 |
Karatsuba's alg for multiplication, Strassen's alg for matrix multiplication, start FFT |
Chapter 2 of Dasgupta etal, notes of Jeff/Sariel |
| Thu, Sept 8 |
Finish FFT, Backtracking and start Dynamic Programming |
|
| Tue, Sept 13 |
Dynamic Programming: Independent Set in Trees, Interval Scheduling, Edit Distance |
Chapter 6 of Dasgupta etal book, Jeff/Sriel/Chandra notes |
| Thu, Sept 15 |
Dynamic Programming: CFG membership (CYK algorithm), Dominating Set in trees, Linear Space for Sequence Alignment |
CYK algorithm, Jeff's notes, Kleinberg-Tardos for sequence alignment |
| Tue, Sept 20 |
Shortest Paths and Negative Cycle Detection |
Jeff/Chandra's notes, Dasgupta etal, Kleinberg-Tardos |
| Thu, Sept 23 |
Greedy algorithms and the exchange argument(s) |
Jeff/Chandra notes, Dasgupta etal, Kleinberg-Tardos |
| Tue, Sept 27 |
Basics of Matroids |
Jeff's notes, lecture notes from Chandra's topics course |
| Thu, Sept 29 |
Midterm 1: 7:00-9:00pm in 101 Transportation Building |
NP-Completeness, reductions, recursion, divide and conquer, dynamic programming, basic probability/randomization |
| Friday, Sept 30 |
Deadline to add a graduate course |
|
| Tue, Oct 4 |
Tail inequalities, Chernoff bound, balls & bins, quick sort |
Sariel's notes for quick sort, Jeff's notes for Chernoff, balls & bins |
| Thu, Oct 6 |
Hashing, Universal hashing |
Jeff/Chandra notes |
| Tue, Oct 11 |
Fingerprinting, Schwartz-Zippel lemma, applications |
Schwartz-Zippel Lemma |
| Thu, Oct 13 |
Network flows: definition, edge vs path formulation, augmenting path algorithm |
Chandra/Jeff/Sariel notes, Kleinberg-Tardos book |
| Friday, Oct 14 |
Deadline to drop a graduate course |
|
| Tue, Oct 18 |
Network flows: maxflow-mincut theorem, polynomial-time algorithms |
Chandra/Jeff/Sariel notes, Kleinberg-Tardos book |
| Thu, Oct 20 |
Network flow applications: disjoint paths, matchings and assignments, project scheduling |
Chandra/Jeff/Sariel notes, Kleinberg-Tardos book |
| Tue, Oct 25 |
Network flow variants: lower bounds, circulations, min-cost flow |
Jeff/Sariel notes, Kleinberg-Tardos book |
| Thu, Oct 27 |
Non-bipartite graph matching |
Notes from Chandra's course on combinatorial optimization |
| Tue, Nov 1 |
Linear Programming: Introduction and Geometry |
Jeff/Sariel notes, Chapter 7 of Dasgupta etal book, Chandra's notes from CS 473 in Fall 2009, Notes (2,3) from Chandra's combinatorial optimization course |
| Thu, Nov 3 |
Midterm 2: 7:00-9:00pm in 101 Transportation Building |
Greedy algorithms, shortest paths, randomization, network flows and applications |
| Tue, Nov 8 |
Linear Programming: Duality and Farkas Lemma |
|
| Thu, Nov 10 |
Linear Programming: Algorithms, applications, polyhedral approach to combinatorial optimization |
|
| Tue, Nov 15 |
Dealing with intractability: heuristics and approximation algorithms |
Jeff/Sariel notes on approximation algorithms, Dasgupta etal Chapter 9, Kleinberg-Tardos Chapters 11-12, Chandra's course on approximation algorithms |
| Thu, Nov 17 |
Approximation algorithms |
|
| Tue/Thu, Nov 22, 24 |
Thanksgiving Break |
|
| Tue, Nov 29 |
Approximation algorithms: Metric-TSP, ATSP, Knapsack |
Jeff/Sariel notes, notes from Chandra's course on approximation algorithms |
| Thu, Dec 1 |
Linear Programming based approximation algorithms: vertex cover, set cover, routing |
|
| Tue, Dec 6 |
Course review, evaluations |
|
| Tue, Dec 13 |
Final Exam: 7:00-10:00 PM in 1TB-103 |
|