Date |
Topic |
Reading |
Homework |
Jan 9 (Mon) |
Introduction on course materials, logistics, and pre-requisites |
|
|
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 Reverse-Delete Algorithm |
KT 4.5 |
|
Jan 25 (Wed) |
Lecture 04: Implementing Kruskal's Algorithm with the Union-Find 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: One-Side Optimality of Gale-Shapley 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 Bellman-Ford Algorithm |
KT 6.7, 6.8 & 6.10 |
|
Apr 5 (Wed) |
Lecture 20: All-Pair Shortest Path Problem
and Floyd-Warshall Algorithm |
Wikipedia page on Floyd-Warshall Algorithm |
|
Apr 10 (Mon) |
Lecture 21: The Maximum Flow Problem
and Ford-Fulkerson 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: Capacity-Scaling 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 |