Spring 2014

(Subject to change at any time)

Week |
Material Covered |
Corresponding Reading |
Homework Assigned |

Week 1: Jan 23 | Stable Matching, Review | Ch.1; also Ch.2, 3, and Discrete Math Handout for the Quiz | None: study for Quiz |

Week 2: Jan 27 and Jan 30 | Quiz on Jan 27Greedy Algorithms: Exchange Argument |
Sec 4.2 | Problem Set 1: Due Thursday, Feb 6 |

Week 3: Feb 3 and 6 | Greedy Algorithms:Shortest Path, MST and Clustering |
Sec 4.4-4.5, 4.7 | Problem Set 2: Due Thursday, Feb 13 |

Week 4: Feb 10 and 13 | Dynamic Programming:Weighted Interval Scheduling, Segmented Least Squares |
Sec 6.1-6.3 | Problem Set 3: Due Thursday, Feb 20 |

Week 5: Feb 18 and 20 | Dynamic Programming:Knapsack, Sequence Alignment, Longest Increasing Subsequence. |
Sec 6.4, 6.6-6.7 | Problem Set 4: Due Thursday, Feb 27 |

Week 6: Feb 24 and Feb 27 | Dynamic Programming: Shortest PathDivide and Conquer: Closest Pair |
Sec 6.8, 5.1-5.4 | Problem Set 5: Due Thursday, Mar 20 |

Week 7: Mar 3 and 6 | Divide and Conquer: Multiplication and FFT Midterm Exam on Mar 3 |
Sec 5.5-5.6 | Study for Midterm Exam |

Week 8: Spring Break |
|||

Week 9: Mar 17 and 20 | Network Flow: Max-Flow Min-Cut, Bipartite Matching, Disjoint Paths(drop deadline is Friday) |
Sec 7.1-7.2, 7.5-7.6 | Problem Set 6: Due Thursday, Mar 27 |

Week 10: Mar 24 and 27 | Network Flow: Circulations, Survey Design, Airline Scheduling |
Sec 7.7-7.9 | Problem Set 7: Due Thursday, Apr 10 |

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

Week 12: Apr 7 and 10 | NP and Computational Intractability |
Sec 8.2-8.7 | Problem Set 8: Due Thursday, Apr 17 |

Week 13: Apr 14 and 17 | NP and Computational Intractability, Dealing with Intractability |
Sec 8.8, 10.1-10.2 | Problem Set 9: Due Monday, Apr 28 |

Week 14: Apr 21 and 24 | Approximation Algorithms |
Sec 11.1 | |

Week 15: Apr 28 and May 1 | Approximation Algorithms, Linear Programming |
Sec 11.4-11.6, 11.8 | |

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

Week 17 | Final Exam on Monday May 12th, 8:00am-11:00am, SAGE 4101(subject to change: please check with Registrar) |