Date 
Topic 
Reading 
Homework 
Jan 9 (Mon) 
Introduction on course materials, logistics, and prerequisites 


Jan 11 (Wed) 
Lecture 01: Interval Scheduling Problem 
KT 4.1 (Before "A Related Problem") 
Homework 1 out 
Jan 18 (Wed) 
Lecture 02: Scheduling All Intervals and Minimum Spanning Trees 
KT 4.1 (After "A Related Problem"), KT 4.5 (before "Analyzing the Algorithms") 

Jan 23 (Mon) 
Lecture 03: Kruskal's Algorithm and the ReverseDelete Algorithm 
KT 4.5 

Jan 25 (Wed) 
Lecture 04: Implementing Kruskal's Algorithm with the UnionFind Data Structure 
KT 4.6 
Homework 1 due Homework 2 out 
Jan 30 (Mon) 
Lecture 05: Prim's Algorithm and Boruvka's Algorithm 
KT 4.5 Wikipedia Page on Boruvka's Algorithm 

Feb 1 (Wed) 
Lecture 06: The Single Source Shortest Path Problem
and Dijkstra's Algorithm 
KT 4.4 

Feb 6 (Mon) 
Lecture 07: The Stable Matching Problem 
KT 1.1 

Feb 8 (Wed) 
Lecture 08: OneSide Optimality of GaleShapley and the Parity of Intervals Problem 

Homework 2 due 
Feb 13 (Mon) 
Midterm 1 


Feb 15 (Wed) 
Lecture 09: Merge Sort and Solving Recurrences 
KT 5.1 & 5.2 
Homework 3 out 
Feb 20 (Mon) 
Lecture 10: Counting Inversions and Peak Finding 
KT 5.3 

Feb 22 (Wed) 
Lecture 11: Integer Multiplication 
KT 5.5 

Feb 27 (Mon) 
Lecture 12: Closest Pair of Points 
KT 5.4 

Mar 1 (Wed) 
Lecture 13: Convolution and Fast Fourier Transform (Part I) 
KT 5.6 
Homework 3 due Homework 4 out 
Mar 6 (Mon) 
Lecture 14: Fast Fourier Transform (Part II) and Introduction to Dynamic Programming 
KT 5.6, 6.1 & 6.2 

Mar 8 (Wed) 
Lecture 15: Segmented Least Squares 
KT 6.3 

Mar 20 (Mon) 
Lecture 16: The Knapsack Problem 
KT 6.4 

Mar 22 (Wed) 
Lecture 17: RNA Secondary Structure 
KT 6.5 
Homework 4 due 
Mar 27 (Mon) 
Midterm 2 


Mar 29 (Wed) 
Lecture 18: Sequence Alignment 
KT 6.6 
Homework 5 out 
Apr 3 (Mon) 
Lecture 19: Linear Space Algorithm for Sequence
Alignment and BellmanFord Algorithm 
KT 6.7, 6.8 & 6.10 

Apr 5 (Wed) 
Lecture 20: AllPair Shortest Path Problem
and FloydWarshall Algorithm 
Wikipedia page on FloydWarshall Algorithm 

Apr 10 (Mon) 
Lecture 21: The Maximum Flow Problem
and FordFulkerson Algorithm 
KT 7.1 

Apr 12 (Wed) 
Lecture 22: The Maximum Flow Minimum Cut Theorem

KT 7.2 
Homework 5 due
Homework 6 out 
Apr 17 (Mon) 
Lecture 23: CapacityScaling Algorithm and
the Maximum Matching Problem 
KT 7.3 

Apr 19 (Wed) 
Lecture 24: Hall's Theorem and
the Image Segmentation Problem

KT 7.5 & 7.10 

Apr 24 (Mon) 
Lecture 25: Baseball Elimination 
KT 7.12 

Apr 26 (Wed) 
Lecture 26: Project Selection 
KT 7.11 
Homework 6 due 