CS 473: Schedule and Lecture Notes

We will provide skeleton slide notes. We recommend reading the excellent notes of Jeff Erickson and Sariel Har-Peled as well as other material that we will provide pointers to. Students are strongly encouraged to consult various sources in addition to the notes linked to from here and from the class resources. 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. Students are strongly encouraged not to miss lectures under the assumption that they can watch the videos – we know that this is slippery slope. The videos are available here. You will need to login with your Illinois NetID and password.

Date Topics Reading
Tue, Jan 16 Administrivia & intro, start of FFT Jeff's notes, Sariel's notes, Wikipedia entry on FFT, Chapter 5 of KT book, Chapter 2 of DPV book
Thu, Jan 18 FFT (tentative slides) In addition to previous pointers, Michel Goemans's notes with background on Fourier Series
Tue, Jan 23 Intro to Dynamic Programming: Edit Distance, Knapsack Jeff's notes, Chapter 6 in Dasgupta etal, Chapter 6 in Kleinberg-Tardos
Thu, Jan 25 Dynamic Programming in trees Same as above. Dominating Set example not in any notes or books.
Tue, Jan 30 Dynamic Programming for Shortest Paths in Graphs Kleinberg-Tardos Chapter 6, Dasgupta etal Chapter 6, Jeff's notes on APSP
Thu, Feb 1 Improving space and time in dynamic programming Jeff's notes, Wikipedia article for Longest Increasing Subsequence
Randomization (In what follows, the topics are tentative)
Tue, Feb 6 Intro to randomized algorithms, Quick Sort Sariel's notes on basic of probability. Jeff's notes on basics and randomized quick sort analysis.
Thu, Feb 8 Slick analysis of Quick sort, and Concentration inequalities Jeff's notes, and Sariel's notes
Tue, Feb 13 W.h.p. analysis and Universal Hashing Sariel's notes on high probability analysis of Qucik sort, and Jeff's notes on hashing.
Thu, Feb 15 Universal hashing and (brief) perfect hashing Jeff's notes on hashing.
Tue, Feb 20 Fingerprinting Notes from a course taught by Avrim Blum and Anupam Gupta
Thu, Feb 22 (Optional) Review for midterm
Mon, Feb 26 Midterm 1: 7:00-9:00pm, 1320 DCL Recursion, divide and conquer, dynamic programming, randomization in algorithms/data structures
Tue, Feb 27 No Lecture due to the midterm on Monday.
Thu, March 1 Streaming Algorithms Jeff's notes, and notes from a course taught by Avrim Blum and Anupam Gupta.
Tue, March 6 Intro to Network Flows and Cuts, Maxflow-mincut theorem Chapter 7 in Kleinberg-Tardos, Jeff's notes
Thu, March 8 Ford-Fulkerson, poly-time algorithms for flow
Fri, March 9 Deadline to drop without a penalty
Tue, March 13 Flow applications including bipartite matching Chapter 7 in Kleinberg-Tardos, Jeff's notes
Thu, March 15 More applications and flow variants. Notes by Kent from the lecture. Chapter 7 in Kleinberg Tardos, Jeff's notes
March 19 - 23Spring Break
Tue, March 27 Linear Programming: Introduction and Geometry, Simplex Method Jeff's notes (up to section 26.4)
Thu, March 29 Simplex and LP Duality, Simplex Implementation. Jeff's notes.
Tue, April 3 Strong Duality Theorem, Integer Programming Jeff's notes
Thu, April 5 Midterm review. (Canceled)
Mon, April 9 Midterm 2, 7-9pm in 1320 DCL.
Tue, April 10 Integer Programming. Reductions and Intractability. Chapter 8 of Kleinberg-Tardos and Dasgupta etal, Jeff's notes
Thu, April 12 SAT, NP, reductions  
Tue, April 17 More NPC reductions Sariel's notes.
Thu, April 19 (Canceled)
Tue, April 24 Dealing with intractability: heuristics and approximation algorithms Jeff notes, Dasgupta etal Chapter 9, Kleinberg-Tardos Chapters 11-12, Chandra's course on approximation algorithms
Thu, April 26 Approximation algorithms: Load balancing, Set Cover  
Tue, May 1 Approximation algorithms: Metric-TSP, ATSP Chandra's notes
Wed, May 9 Review for the final exam  
Fri, May 11 Final Exam: 7:00-10:00pm