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