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 at here.

Date Topics Reading
Wed, Aug 24 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
Fri, Aug 26 FFT In addition to previous pointers, Michel Goemans's notes with background on Fourier Series
Wed, Aug 31 Intro to Dynamic Programming: Edit Distance, Knapsack Jeff's notes, Chapter 6 in Dasgupta etal, Chapter 6 in Kleinberg-Tardos
Fri, Sep 2 Dynamic Programming in trees Same as above. Dominating Set example not in any notes or books.
Wed, Sep 7 Dynamic Programming for Shortest Paths in Graphs Kleinberg-Tardos Chapter 6, Dasgupta etal Chapter 6, Jeff's notes on APSP
Fri, Sep 9 Improving space and time in dynamic programming Jeff's notes, Wikipedia article for Longest Increasing Subsequence
Wed, Sep 14 Intro to randomized algorithms, Quick Sort Sariel's notes on basic of probability. Jeff's notes on basics and randomized quick sort analysis.
Fri, Sep 16 Slick analysis of Quick sort, and Concentration inequalities Jeff's notes, and Sariel's notes
Wed, Sep 21 W.h.p. analysis, and Universal Hashing Sariel's notes on high probability analysis of Qucik sort, and Jeff's notes on hashing.
Fri, Sep 23 Universal hashing and (brief) perfect hashing Jeff's notes on hashing.
Wed, Sep 28 Fingerprinting Notes from a course taught by Avrim Blum and Anupam Gupta
Fri, Sep 30 Review for midterm
Mon, Oct 3 Midterm 1: 7:00-9:00pm, 1320 DCL Recursion, divide and conquer, dynamic programming, randomization in algorithms/data structures
Wed, Oct 5 Streaming Algorithms Jeff's notes, and notes from a course taught by Avrim Blum and Anupam Gupta.
Fri, Oct 7 Intro to Network Flows, Ford-Fulkerson Chapter 7 in Kleinberg-Tardos, Jeff's notes
Wed, Oct 12 Maxflow-mincut theorem, poly-time algorithms for flow
Fri, Oct 14 Flow applications including bipartite matching
Deadline to drop without a penalty
Chapter 7 in Kleinberg-Tardos, Jeff's notes
Wed, Oct 19 Catch up lecture
Fri, Oct 21 More applications and flow variants Chapter 7 in Kleinberg Tardos, Jeff's notes
Wed, Oct 26 Linear Programming: Introduction and Geometry, Simplex Method (with class notes) Jeff's notes (up to section 26.4)
Fri, Oct 28 Simplex and LP Duality (with class notes) Jeff's notes.
Wed, Nov 2 LP Duality Jeff's notes
Fri, Nov 4 Midterm review, no lecture
Mon, Nov 7 Midterm 2: 7:00-9:00pm, 1320 DCL
Wed, Nov 9 Reductions and intractability Chapter 8 of Kleinberg-Tardos and Dasgupta etal, Jeff's notes
Fri, Nov 11 SAT, NP, reductions  
Wed, Nov 16 More NPC reductions  
Fri, Nov 18 Dealing with intractability: heuristics and approximation algorithms Jeff notes, Dasgupta etal Chapter 9, Kleinberg-Tardos Chapters 11-12, Chandra's course on approximation algorithms
Nov 21 to 25 Thanksgiving Break  
Wed, Nov 30 Approximation algorithms: Load balancing, Set Cover  
Fri, Dec 2 Approximation algorithms: Metric-TSP, ATSP
ICES Forms
Chandra's notes
Wed, Dec 7 Review for final exam  
Fri, Dec 9 Final Exam: 7:00-10:00pm, 112 Huff Hall