Spring 2019

(Subject to change at any time)

Week |
Material Covered |
Corresponding Reading |
Homework Assigned |

Week 1: Jan 11 | Stable Matching, Review | Ch.1; also Ch.2, 3, and Discrete Math Handout | |

Week 2: Jan 15 and 18 | Greedy Algorithms: Exchange Argument, Shortest Path |
Sec 4.1-4.2, 4.4 | Problem Set 1: Due Friday, Jan 25 |

Week 3: Jan 22 and 25 | Greedy Algorithms: MST and ClusteringDynamic Programming:Weighted Interval Scheduling |
Sec 4.5, 4.7, 6.1-6.2 | Problem Set 2: Due Friday, Feb 1 |

Week 4: Jan 29 and Feb 1 | Dynamic Programming: Segmented Least Squares, Longest Increasing Subsequence, Knapsack |
Sec 6.3-6.4 | Problem Set 3: Due Friday, Feb 8 |

Week 5: Feb 5 and 8 | Dynamic Programming: Sequence Alignment, Shortest Path |
Sec 6.6-6.8 | Problem Set 4: Due Friday, Feb 22 |

Week 6: Feb 12 and 15 | Midterm Exam on February 15 |
Study for Midterm Exam | |

Week 7: Feb 22 | Divide and Conquer: Closest Pair |
Sec 5.1-5.4 | |

Week 8: Feb 26 and Mar 1 | 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 5: Due Friday, Mar 15 |

Week 9: Spring Break |
|||

Week 10: Mar 12 and 15 | Network Flow: Circulations, Survey Design, Airline Scheduling |
Sec 7.7-7.9 | |

Week 11: Mar 19 and 22 | Network Flow: Image Segmentation, Project SelectionDivide and Conquer: Multiplication and Fast Fourier Transform |
Sec 7.10-7.11, Sec 5.6 | |

Week 12: Mar 26 and 29 | NP and Computational Intractability |
Sec 8.1-8.4 | |

Week 13: Apr 2 and 5 | NP and Computational Intractability |
Sec 8.5, 8.7-8.8 | |

Week 14: Apr 9 and 12 | Dealing with Intractability, Approximation Algorithms |
Sec 10.1-10.2, 11.1 | |

Week 15: Apr 16 and 19 | Approximation Algorithms, Linear Programming |
Sec 11.6, 11.8 | |

Week 16: Apr 23 and 26 | Approximation Algorithms, Local Search |
Sec 13.4, 12.1-12.4 | Paper report due (students registered for CSCI 6020 only) |

Week 17 | Final Exam during finals week (time and place subject to change: please check with Registrar) |