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 - 23 | Spring 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 | |