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.
- Jeff Erickson's notes, homeworks, and exams from previous semesters
- Jeff Erickson: CS 573 (Fall 2010)
- Sariel Har-Peled: CS 573 (Fall 2009)
- Chandra Chekuri: CS 473 (Fall 2010)
- Algorithms text book by Dasgupta, Papadimitriou and Vazirani.
- Algorithm Design by Kleinberg and Tardos. Lecture slides based on the book available here.
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