Class Schedule

Spring 2016
(Subject to change at any time)


Week Material Covered Corresponding Reading Homework Assigned
Week 1: Jan 26 and 29 Stable Matching, Review
Quiz 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 Clustering
Dynamic 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 Path
Divide 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, SAGE 3510
(time and place subject to change: please check with Registrar)