Class Schedule

Spring 2018
(Subject to change at any time)


Week Material Covered Corresponding Reading Homework Assigned
Week 1: Jan 16 and 19 Stable Matching, Review
Quiz on Jan 19
Ch.1; also Ch.2, 3, and Discrete Math Handout for the Quiz None: study for Quiz
Week 2: Jan 23 and 26 Greedy Algorithms: Exchange Argument, Shortest Path Sec 4.1-4.2, 4.4 Problem Set 1: Due Friday, Feb 2
Week 3: Jan 30 and Feb 2 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 9
Week 4: Feb 6 and 9 Dynamic Programming: Segmented Least Squares, Longest Increasing Subsequence, Knapsack Sec 6.3-6.4 Problem Set 3: Due Friday, Feb 16
Week 5: Feb 13 and 16 Dynamic Programming: Sequence Alignment, Shortest Path Sec 6.6-6.8 Problem Set 4: Due Friday, Feb 23
Week 6: Feb 23 Divide and Conquer: Closest Pair
Sec 5.1-5.4 Study for Midterm Exam
Week 7: Feb 27 and Mar 2 Midterm Exam on February 27
Divide and Conquer: Multiplication and Fast Fourier Transform
Sec 5.6
Week 8: Mar 6 and 9 Network Flow: Max-Flow Min-Cut, Bipartite Matching, Disjoint Paths
(drop deadline is Friday)
Sec 7.1-7.2, 7.5-7.6
Week 9: Spring Break
Week 10: Mar 20 and 23 Network Flow: Circulations, Survey Design, Airline Scheduling
Sec 7.7-7.9
Week 11: Mar 27 and 30 Network Flow: Image Segmentation, Project Selection.
NP and Computational Intractability
Sec 7.10-7.11, 8.1
Week 12: Apr 3 and 6 NP and Computational Intractability Sec 8.2-8.7
Week 13: Apr 10 and 13 NP and Computational Intractability, Dealing with Intractability Sec 8.8, 10.1-10.2
Week 14: Apr 17 and 20 Approximation Algorithms, Linear Programming Sec 11.1, 11.6
Week 15: Apr 24 and 27 Approximation Algorithms Sec 11.8, 13.4
Week 16: May 1 Local Search Sec 12.1-12.4 Paper report due
(students registered for CSCI 6210 only)
Week 17 Final Exam, date and time TBD