CS 573: Schedule and Lecture Notes

There is no plan to give explicit lecture notes this semester. Jeff Erickson and Sariel Har-Peled have excellent sets of notes and the instructor will give pointers to them as well as other material available on the web as needed. Students are strongly encouraged to consult various sources in addition to the notes linked to from here. Several algorithms textbooks are on reserve in Grainger Library, and many complete sets of course materials can be found on the web.

Lectures will be video taped since this course is being offered as an online course. On-campus students are strongly encouraged not to miss lectures under the assumption that they can watch the videos - you and I know that this is slippery slope. The videos are available here.

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