| Date | Assignment | Reading | Subject | |
|---|---|---|---|---|
| Jan 23 | Administrivia, what's this course about? | |||
| Jan 25 | Stable Matching problem; proving termination, correctness, efficiency | |||
| Jan 28 | Interval Scheduling problem; brute force and greedy algorithms; sorting algorithms | |||
| Jan 30 | Interval Scheduling, continued | |||
| Feb 01 | Shaffer 1, CLRS 1, How to get hired at Google | Independent set, facility location, etc. | ||
| Feb 05 | Last day to add classes | |||
| Feb 04 | Shaffer 2, CLRS 2 | Mathematical preliminaries; discuss pre-test if necessary | ||
| Feb 06 | Shaffer 3 | Asymptotic analysis | ||
| Feb 08 | HW1 | CLRS 3 | More on asymptotic analysis | |
| Feb 11 | CLRS 4 | Divide-and-conquer algorithms | ||
| Feb 13 | Shaffer 7.1-7.4 | Some sorting algorithms | ||
| Feb 15 | Shaffer 5.5 and 7.6; CLRS 6 | Heaps and heap-sort | ||
| Feb 18 | HW1 due | Present & discuss HW1 | ||
| Feb 20 | Last day to drop classes | |||
| Feb 20 | Shaffer 7.5, CLRS 7 | Present & discuss HW1 | ||
| Feb 22 | Shaffer 7.8-7.9, CLRS 8.1 | Present & discuss HW1 | ||
| Feb 25 | Shaffer 7.7, CLRS 8 | Present & discuss HW1; lower bounds proofs | ||
| Feb 27 | HW2 | Shaffer 7.7, CLRS 8 | Why you can't sort in linear time, and how to do it | |
| Mar 01 | CLRS 9 | Not quite sorting | ||
| Mar 04 | Shaffer 16.1, CLRS 15.1 | Dynamic programming | ||
| Mar 06 | CLRS 15.2-15.3 | More dynamic-programming examples | ||
| Mar 08 | CLRS 15.4-15.5 | More dynamic-programming examples | ||
| 3/11-3/17 | Spring break | |||
| Mar 18 | HW2 due | Present & discuss HW2 | ||
| Mar 20 | Present & discuss HW2 | |||
| Mar 22 | Present & discuss HW2 | |||
| Mar 25 | Present & discuss HW2 | |||
| Mar 27 | Last day to withdraw from classes | |||
| Mar 27 | Present & discuss HW2 | |||
| Mar 29 | Shaffer 5.6, CLRS 16.1-16.3 | Greedy algorithms; Huffman codes | ||
| Apr 01 | Shaffer 11.1-11.3, CLRS 22 | Graph basics: nodes, edges, paths, Eulerian paths, degrees | ||
| Apr 03 | CLRS 22 | More on graphs: list and matrix representations, breadth-first and depth-first search | ||
| Apr 05 | CLRS 22 | More on graphs: properties of breadth-first and depth-first search | ||
| Apr 08 | CLRS 22 | More on graphs: applications of breadth-first and depth-first search | ||
| Apr 10 | Research day: no classes | |||
| Apr 12 | Return & discuss homework 1 | |||
| Apr 15 | Shaffer 11.5, CLRS 23 | Minimum spanning trees | ||
| Apr 17 | Shaffer 11.5, CLRS 23 | Minimum spanning trees | ||
| Apr 19 | HW3 | Shaffer 11.4, CLRS 24-24.3 | Single-source shortest paths | |
| Apr 22 | HW2 resubmission due | CLRS 26.1-26.3 | Maximum flow problems | |
| Apr 24 | Computability, decidability, and semidecidability | |||
| Apr 26 | Shaffer 17.3 | Uncomputability | ||
| Apr 29 | Shaffer 17.1 | Problem reductions and uncomputability; completeness; Rice's theorem? | ||
| May 01 | CLRS 34.1-34.2 | Polynomial-time computability, decidability, and semidecidability | ||
| May 03 | Shaffer 17.2; CLRS 34.3-34.5 | Polynomial-time reductions; NP and NP-completeness | ||
| May 06 | HW3 due | Present & discuss HW3 | ||
| May 08 | Present & discuss HW3 | |||
| May 9-10 | emergency make-up days | |||
| May 17 | present & discuss, 10:30 AM-12:30 PM | |||