| Date | Topic | Reading | Problem sets |
|---|---|---|---|
| Sep 4 | Stable matching; representative problems |
KT 1.1-1.2 |
|
| Sep 8 | Algorithm efficiency; Stable matching implementation |
KT 2.1-2.3 |
PS1 out |
| Sep 11 | Asymptotic order of growth |
KT 2.2, 2.4
DPV 0.3
|
|
| Sep 15 | Priority queues data structure |
KT 2.5
DPV 4.5
|
|
| Sep 18 |
Graphs and graph traversals
Graph traversal using stacks and queues
|
KT 3.1-3.3
DPV 3.1 - 3.3
|
PS1 due
PS2 out
|
| Sep 22 |
DAGs and topological ordering
Strong connectivity in directed graphs
|
KT 3.5, 3.6
DPV 3.4
|
|
| Sep 25 | Greedy algorithms: Scheduling |
KT 4.1 |
|
| Sep 29 | Shortest paths |
KT 4.4
DPV 4.4 - 4.7
|
PS2 due
PS3 out
|
| Oct 2 | Minimum spanning trees |
KT 4.5
DPV 5.1
|
|
| Oct 6 | Kruskal's algorithm implementation |
KT 4.6
DPV 5.1
|
PS3 due |
| Oct 9 | Midterm 1 |
PS4 out |
|
| Oct 13 | Columbus Day, no class |
||
| Oct 16 | Divide-and-conquer: Mergesort |
KT 5.1
DPV 2.3
|
|
| Oct 20 | Solving recurrence relations |
KT 5.1-5.2
DPV 2.2
|
|
| Oct 23 | Finding closest pair of points |
KT 5.4 |
PS4 due
PS5 out
|
| Oct 27 | Dynamic programming: Weighted interval scheduling |
KT 6.1-6.2 |
|
| Oct 30 | Shortest paths with negative weights |
KT 6.8
DPV 4.6
|
|
| Nov 3 |
Knapsack
Sequence alignment
|
KT 6.4, 6.6
DPV 6.3, 6.4
|
|
| Nov 6 | Network flows: Ford-Fulkerson algorithm |
KT 7.1-7.3
DPV 7.2
|
PS5 due
PA out
|
| Nov 10 | Midterm 2 (tentative) |
||
| Nov 13 | Maximum flow and minimum cuts |
KT 7.1-7.3 |
|
| Nov 17 |
Bipartite matching
Image segmentation
|
KT 7.5, 7.10 |
PS6 out |
| Nov 20 | Flows and cuts: Project selection |
KT 7.11
DPV 7.3
|
|
| Nov 24 | SAT, NP, and NP-completeness |
KT 8.1-8.2
DPV 8.1-8.2
|
PA due |
| Nov 27 | Thanksgiving Day, no class |
||
| Dec 1 | NP-completeness reductions |
KT 8.3-8.4
DPV 8.3
|