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.
-- All dates below are tentative and only intended to give an outline of the course --
http://jeffe.cs.illinois.edu/teaching/algorithms/book/03-dynprog.pdf
| Date | Topics | Reading |
|---|---|---|
| Tue, Jan 26 | 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 28 | FFT | In addition to previous pointers, Michel Goemans's notes with background on Fourier Series |
| Tue, Feb 2 | Intro to Dynamic Programming: Edit Distance, Knapsack | Jeff's notes, Chapter 6 in Dasgupta etal, Chapter 6 in Kleinberg-Tardos |
| Thu, Feb 4 | Dynamic Programming in trees | Same as above. Dominating Set example not in any notes or books. |
| Tue, Feb 9 | Dynamic Programming for Shortest Paths in Graphs | Kleinberg-Tardos Chapter 6, Dasgupta etal Chapter 6, Jeff's notes on APSP |
| Thu, Feb 11 | 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 16 | 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 18 | Slick analysis of Quick sort, and Concentration inequalities | Jeff's notes, and Sariel's notes |
| Tue, Feb 23 | 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 25 | Universal hashing and (brief) perfect hashing | Jeff's notes on hashing. |
| Tue, March 2 | Fingerprinting | Notes from a course taught by Avrim Blum and Anupam Gupta |
| Thu, March 4 | Optional review session for midterm 1 | |
| Mon, March 8 | Midterm 1: Online, 7-9pm, Upload from 9pm to 10pm | Recursion, divide and conquer, dynamic programming, randomization in algorithms/data structures |
| Tue, March 9 | No Lecture due to Midterm 1 | |
| Thu, March 11 | Streaming Algorithms | Jeff's notes, and notes from a course taught by Avrim Blum and Anupam Gupta. |
| Tue, March 16 | Intro to Network Flows and Cuts, Maxflow-mincut theorem | Chapter 7 in Kleinberg-Tardos, Jeff's notes |
| Thu, March 18 | Ford-Fulkerson, poly-time algorithms for flow | |
| Tue, March 23 | Flow applications including bipartite matching | Chapter 7 in Kleinberg-Tardos, Jeff's notes |
| Thu, March 25 | More applications | Chapter 7 in Kleinberg Tardos, Jeff's notes |
| Tue, March 30 | Flow applications and flow variants. Intro to Linear Programming | Flows: Chapter 7 in Kleinberg Tardos, Jeff's notes. LP: Jeff's notes (first two pages) |
| Thu, April 1 | Linear Programming: Geometry, Simplex algorithm, and LP Duality. | Jeff's notes (up to section 26.4). |
| Tue, April 6 | Cancelled | |
| Sat, April 10 | Midterm2 review done during an extra office hours. | |
| Mon, Apr 12 | Midterm 2: Online, 7-9pm, Upload from 9pm to 10pm | |
| Tue, Apr 13 | Break day -- no lecture. | |
| Thu, Apr 15 | Strong Duality Theorem, Integer Programming | Jeff's notes |
| Tue, Apr 20 | Integer Programming. Reductions and SAT. | Chapter 8 of Kleinberg-Tardos and Dasgupta etal, Jeff's notes |
| Thu, Apr 22 | Intractability, NP, example reductions | |
| Tue, Apr 27 | NPC reductions, Dealing with Intractability: Heuristics and approximation algorithms | Sariel's notes on NPC. Jeff notes, Dasgupta etal Chapter 9, Kleinberg-Tardos Chapters 11-12, Chandra's course on approximation algorithms |
| Thu, Apr 29 | Approximation algorithms: Load balancing, Set Cover | Jeff notes, Dasgupta etal Chapter 9, Kleinberg-Tardos Chapters 11-12, Chandra's course on approximation algorithms |
| Tue, May 4 | Approximation algorithms: Metric-TSP, ATSP | Chandra's notes |
| Wed, May 5 | Review for the final exam (annotated slides) | |
| Wed, May 5 | Deadline to drop without a grade of W | |
| Mon, May 10 | Final Exam. 7 - 10pm online, 10 - 11pm scan and upload | Everything covered. |