Class Schedule

Spring 2008
(Subject to change at any time)

Week	Material Covered	Corresponding Reading	Homework Assigned
Week 1: Jan 14 and 17	Stable Matching	Ch.1; also Ch.2,3 and Discrete Math Handout for the Quiz	None: study for Quiz
Week 2: Jan 24	Quiz on Jan 24.		Problem Set 1: Due Thursday, Jan 31
Week 3: Jan 28 and 31	Greedy Algorithms: Interval Scheduling, Exchange Argument, Scheduling to Minimize Lateness.	Sec 4.1-4.2	Problem Set 2: Due Thursday, Feb 7
Week 4: Feb 4 and 7	Greedy Algorithms: Shortest Path, MST, and Clustering.	Sec 4.4-4.7	Problem Set 3: Due Thursday, Feb 14
Week 5: Feb 11 and 14	Divide and Conquer. Dynamic Programming: Weighted Interval Scheduling	Sec 5.1-5.4, 6.1-6.2	Problem Set 4: Due Thursday, Feb 21
Week 6: Feb 19 and 21	Dynamic Programming: Segmented Least Squares, Knapsack	Sec 6.3-6.4	Problem Set 5: Due Thursday, Mar 6
Week 7: Feb 25 and 28	Dynamic Programming: Longest Palindromic Subsequence. Midterm Exam on Feb 28	Sec 6.5
Week 8: Mar 3 and 6	Dynamic Programming: Sequence Alignment, Shortest Path. (drop deadline is Friday)	Sec 6.6, 6.8	Problem Set 6: Due Thursday, Mar 20
Week 9: Spring Break
Week 10: Mar 17 and 20	Network Flow: Ford-Fulkerson, Max-Flow Min-Cut	Sec 7.1-7.3	Problem Set 7: Due Thursday, Mar 27
Week 11: Mar 24 and 27	Network Flow: Bipartite Matching, Disjoint Paths, Circulations	Sec 7.5-7.7	Problem Set 8: Due Thursday, Apr 3
Week 12: Mar 31 and Apr 3	Network Flow: Survey Design, Image Segmentation, Project Selection	Sec 7.8,7.10-7.11	Problem Set 9: Due Thursday, Apr 10
Week 13: Apr 7 and 10	NP and Computational Intractability	Sec 8.1-8.4	Problem Set 10: Due Thursday, Apr 24
Week 14: Apr 14 and 17	NP and Computational Intractability, Special Cases of NP-Hard Problems	Sec 8.5-8.8, Sec 10.1-10.2
Week 15: Apr 21 and 24	Approximation Algorithms, Local Search	Sec 11.8, 12.1-12.4
Week 16: Apr 28	Randomized Algorithms	Sec 13.4
Week 17	Final Exam on Monday, May 5th, 11:30am-2:30pm, Sage 5510 (subject to change: please check with Registrar)