Extra OHs: Friday, May 31, 9:30-10:20am and Monday, June 3, 2:30-3:20pm, PDL C-439 and Zoom

Lecture Notes

Gradescope

Discussion Board

Combinatorial Optimization by Cook, Cunningham, Pulleyblank, Schrijver

Computational Complexity: A Modern Approach by Arora, Barak

Week | Topic | Reading | Homework |
---|---|---|---|

March 25 - 29 | Introduction, Graph Theory, TSP Notes: 03/25, 03/27, 03/29 | 1.1, 1.2, 1.3 TSP | HW 1 due April 4 (.tex, .pdf) |

April 1 - 5 | Minimum spanning trees, shortest paths Notes: 04/01, 04/03, 04/05 | 2.1, 3.1 | HW 2 due April 11 (.tex, .pdf) |

April 8 - 12 | Shortest paths Notes: 04/08, 04/10, 04/12 | 3.1, 3.2, 3.3,
4 recent progress | HW 3 due April 18 (.tex, .pdf) |

April 15 - 19 | Networks Flows, MinCut Notes: 04/15, 04/17, 04/19 | 4.1, 4.2, 4.3 | HW 4 due April 25 (.tex, .pdf) |

April 22 - 26 | Bipartite Matchings, Linear Programming Notes: 04/22, 04/24, 04/26 | 4.4, 5 | Midterm May 1 |

April 29 - May 3 | Linear Programming Notes: 04/29, 05/03 | 5.1, 5.4 | HW 5 due May 9 (.tex, .pdf) |

May 6 - 10 | Total unimodularity Notes: 05/06, 05/08, 05/10 | 5.3, 5.4, 6.1 | HW 6 due May 16 (.tex, .pdf) |

May 13 - 17 | Applications, Branch and Bound Notes: 05/13, 05/15, 05/17 | 6.2, 6.3, 7 | HW 7 due May 23 (.tex, .pdf) |

May 20 - 24 | Branch and Bound, Non-bipartite matchings Notes: 05/20, 05/22, 05/24 | 8.1, 8.2, 8.3 | HW 8 due May 31 (.tex, .pdf) |

May 29 - 31 No class May 27 | Approximation algorithms,
review Notes: 05/29 | ||

June 4 | Final Exam | Seating Chart |