Class Schedule

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 Clustering
Dynamic 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 Selection
Divide 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)