Class Schedule

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 27
Greedy 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 Path
Divide 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.6, 11.8, 13.4
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)