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 |