| Tue Jan 13 | Introduction and course logistics | hw1 out, due Jan 18 | |
|---|---|---|---|
| Thu Jan 15 | Knapsack Dynamic Programs | recitation 1 | |
| Tue Jan 20 | DAGs and Dynamic Programming | oral hw1 out, due week of Jan 25-30 | |
| Thu Jan 22 | Prefix/Interval Dynamic Programming | quiz 1 | |
| Tue Jan 27 | Tree dynamic programming. | hw2 out, due Feb 1 | |
| Thu Jan 29 | Range Operations | ||
| Tue Feb 3 | "Segment trees" | oral hw2 out, due week of Feb 8 - 13 | |
| Thu Feb 5 | String hashing | quiz 2 | |
| Tue Feb 10 | Union find, merging sets | ||
| Thu Feb 12 | Stacks/queues and amortized analysis I | hw3 out, due Feb 22 | |
| Tue Feb 17 | Amortized analysis II | ||
| Thu Feb 19 | Midterm 1 | DP, range operations | |
| Tue Feb 24 | Greedy algorithms, exchange method | hw 4 out, due Mar 8 | |
| Thu Feb 26 | Greedy, regret method, flows I: Ford-Fulkerson | quiz 3, Mar 2--6 spring break | |
| Tue Mar 10 | Flows II: maxflow-mincut, capacity scaling. | hw 5 out, due Mar 13 | |
| Thu Mar 12 | Greedy, regret method, flows III / intro to linear programs | quiz 4 | |
| Tue Mar 17 | Linear programming duality. | oral hw3 out, due week of Mar 22-27 | |
| Thu Mar 19 | Zero sum games | quiz 5 | |
| Tue Mar 24 | TBD | TBD | |
| Thu Mar 26 | TBD | hw6 out, due Apr 12, TBD | |
| Tue Mar 31 | TBD | TBD | |
| Thu Apr 2 | Midterm 2 | amortized analysis, greedy, flows, linear programs | |
| Tue Apr 7 | no lecture Apr 9 due to carnival | ||
| Tue Apr 14 | TBD | TBD + oral hw4 out, due week of Apr 20 - 24 | |
| Thu Apr 16 | TBD | TBD + quiz 6 | |
| Tue Apr 21 | TBD | TBD | |
| Thu Apr 23 | TBD | TBD | |
| TBD, 3 hrs | Final exam | data structures, optimization, computational models | |