Spring 2016

(Subject to change at any time)

Week |
Material Covered |
Corresponding Reading |
Homework Assigned |

Week 1: Jan 26 and 29 | Stable Matching, ReviewQuiz on Jan 29
| Ch.1; also Ch.2, 3, and Discrete Math Handout for the Quiz | None: study for Quiz |

Week 2: Feb 2 and 5 | Greedy Algorithms: Exchange Argument, Shortest Path |
Sec 4.2, 4.4 | Problem Set 1: Due Friday, Feb 12 |

Week 3: Feb 9 and 12 | Greedy Algorithms: MST and ClusteringDynamic Programming:Weighted Interval Scheduling |
Sec 4.5, 4.7, 6.1-6.2 | Problem Set 2: Due Friday, Feb 19 |

Week 4: Feb 19 | Dynamic Programming: Segmented Least Squares |
Sec 6.3 | Problem Set 3: Due Friday, Feb 26 |

Week 5: Feb 23 and 26 | Dynamic Programming: Longest Increasing Subsequence, Knapsack, Sequence Alignment |
Sec 6.4, 6.6-6.7 | Problem Set 4: Due Friday, Mar 4 |

Week 6: Mar 1 and 4 | Dynamic Programming: Shortest PathDivide and Conquer: Closest Pair |
Sec 6.8, 5.1-5.4 | Problem Set 5: Due Friday, Mar 25 |

Week 7: Mar 8 and 11 | Midterm Exam on Mar 8 (drop deadline is Friday)Divide and Conquer: Multiplication and Fast Fourier Transform |
Sec 5.6 | Study for Midterm Exam |

Week 8: Spring Break |
|||

Week 9: Mar 22 and 25 | Network Flow: Max-Flow Min-Cut, Bipartite Matching, Disjoint Paths |
Sec 7.1-7.2, 7.5-7.6 | Problem Set 6: Due Friday, Apr 1 |

Week 10: Mar 29 and Apr 1 | Network Flow: Circulations, Survey Design, Airline Scheduling |
Sec 7.7-7.9 | Problem Set 7: Due Friday, Apr 15 |

Week 11: Apr 5 and 8 | Network Flow: Image Segmentation, Project Selection.NP and Computational Intractability |
Sec 7.10-7.11, 8.1 | |

Week 12: Apr 12 and 15 | NP and Computational Intractability |
Sec 8.2-8.7 | Problem Set 8: Due Friday, Apr 22 |

Week 13: Apr 19 and 22 | NP and Computational Intractability, Dealing with Intractability |
Sec 8.8, 10.1-10.2 | Problem Set 9: Due Tuesday, May 3 |

Week 14: Apr 26 and 29 | Approximation Algorithms, Linear Programming |
Sec 11.1, 11.6 | |

Week 15: May 3 and 6 | Approximation Algorithms |
Sec 11.8, 13.4 | |

Week 16: May 10 | Local Search |
Sec 12.1-12.4 | |

Week 17 | Final Exam on Thursday, May 19, 3-6pm(time and place subject to change: please check with Registrar) |