| Date | Assignment | Reading | Subject |
|---|---|---|---|
| Jan 24 | Administrivia, what's this course about? | ||
| Jan 27 | how to get hired at Google | Stable Matching problem; proving termination, correctness, efficiency | |
| Jan 29 | Interval Scheduling problem; brute force and greedy algorithms | ||
| Jan 31 | Interval Scheduling, continued; proofs of correctness | ||
| Feb 03 | HW1 | No class due to weather | |
| Feb 04 | Last day to add classes | ||
| Feb 05 | No class due to weather | ||
| Feb 07 | Shaffer 1-3, CLRS 1, 3 | Mathematical preliminaries; asymptotic analysis | |
| Feb 10 | |||
| Feb 12 | CLRS 4 | Divide-and-conquer algorithms; solving recurrences | |
| Feb 14 | Shaffer 14 | The same, Shaffer's way | |
| Feb 17 | HW1 due | Present & discuss HW1 | |
| Feb 19 | Present & discuss HW1 | ||
| Feb 19 | Last day to drop classes | ||
| Feb 21 | HW2 | Present & discuss HW1 | |
| Feb 24 | Shaffer 7.1-7.4 | MM's presentation; Some sorting algorithms | |
| Feb 26 | Shaffer 7.5, CLRS 7 | Quicksort | |
| Feb 28 | Shaffer 7.8-7.9, CLRS 8.1 | Empirical analyses, lower bounds for sorting | |
| Mar 03 | Shaffer 7.7, CLRS 8.2-4 | Counting, radix, and bin/bucket sorts | |
| Mar 05 | CLRS 9 | Not quite sorting | |
| Mar 07 | HW2 due | Present & discuss HW2 | |
| Mar 10 | Present & discuss HW2 | ||
| Mar 12 | Present & discuss HW2 | ||
| Mar 14 | Class cancelled due to illness | ||
| Mar 17-23 | Spring break | ||
| Mar 24 | HW3 | Shaffer 16.1, CLRS 15.1 | Dynamic programming |
| Mar 26 | Present & discuss HW2 | ||
| Mar 28 | Present & discuss HW2; discuss dynamic programming | ||
| Mar 28 | Last day to withdraw from classes | ||
| Mar 31 | CLRS 15.2-15.3 | More dynamic-programming examples | |
| Apr 02 | CLRS 15.4-15.5 | More dynamic-programming examples; dynamic programming vs. greedy | |
| Apr 04 | CLRS 16.1-16.2 | Dynamic programming & greedy algorithms | |
| Apr 07 | HW3 due | Present & discuss HW3 | |
| Apr 09 | HW4 | Present & discuss HW3 | |
| Apr 10 | Present & discuss HW3 | ||
| Apr 11 | Shaffer 11.1-11.3, CLRS 22 | Graph basics | |
| Apr 14 | Shaffer 11.5, CLRS 23 | Minimum spanning trees | |
| Apr 16 | CLRS 21 | disjoint-set data structures | |
| Apr 17 | Shaffer 11.4, CLRS 24.1-24.3 | Shortest paths | |
| Apr 18 | CLRS 25 | All-pairs shortest paths | |
| Apr 21 | CLRS 26.1-26.3 | Maximum flow problems | |
| Apr 23 | HW4 due | Present & discuss HW4 | |
| Apr 24 | HW5 | Present & discuss HW4 | |
| Apr 25 | Present & discuss HW4 | ||
| Apr 28 | Shaffer 15 | Proving that things are hard; lower bounds | |
| Apr 30 | Shaffer 17.1, 17.3 | Problem reduction; Computability, decidability, semidecidability, undecidability; Rice's theorem? | |
| May 02 | Shaffer 17.2, CLRS 34 | Polynomial-time computability, polynomial-time reductions, P vs. NP, NP-completeness | |
| May 05 | HW5 due | Present & discuss HW5 | |
| May 07 | Present & discuss HW5; discuss final exam | ||
| May 09 | Dr. Bloch out of town | ||
| May 14 | final exam, 10:30 AM-12:30 PM | ||