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 |