| Date |
Lecture |
Topic |
Reference |
| Jan 12 |
1 |
Introduction |
[Er0] |
| Jan 17 |
2 |
Ranking I: Divide & Conquer, mergesort |
[DPV2,Er1] |
| Jan 19 |
3 |
Ranking II: Randomized divide & conquer, quick sort |
[Er1, Ed2] |
| Jan 24 |
4 |
Ranking III: Median and order statistics |
[DPV2,Er1] |
| Jan 26 |
5 |
Data Structure I: Balanced binary search trees |
[CLRS12-13] |
| Jan 31 |
6 |
Graph Traversal I: Depth first search, topological sort |
[DPV3,Er6] |
| Feb 2 |
7 |
Guest Lecture I: Thomas Molhave |
|
|
|
Graph Traversal II: Breadth first search |
[DPV4,Er5] |
| Feb 7 |
8 |
Shortest paths I: Dijkstra’s algorithm |
[DPV4,Er8] |
| Feb 9 |
9 |
Shortest paths II: Bellman-Ford, Floyd-Warshall |
[DPV4,Er8,9] |
| Feb 14 |
10 |
Dynamic Programming I: Sequence alignment |
[DPV6,Er3] |
| Feb 16 |
11 |
Dynamic Programming II: Knapsack, scheduling |
[DPV6,Er3] |
| Feb 21 |
12 |
Dynamic Programming III: Reinforcement learning |
[RN17] |
| Feb 23 |
13 |
Greedy I: Scheduling & compression |
[DPV5,Er4] |
| Feb 28 |
14 |
Greedy II: Minimum Spanning Tree |
[DPV5,Er7] |
| Mar 2 |
Exam |
Midterm I (Lectures 1-12) |
|
| Mar 7 |
15 |
Greedy III: Clustering |
[CLRS33, Ph8] |
| Mar 9 |
16 |
Cuts & Flows I: Max-flow and min-cut |
[Er10] |
| Mar 21 |
17 |
Cuts & Flows II: Computing flows |
[Er10] |
|
|
Guest Lecture II: Alex Beutel |
[Er11] |
| Mar 23 |
18 |
Cuts & Flows III: Maximum and stable matching |
max. matching: [Er11.3, CLRS26.3] stable matching: [Roth1982] |
| Mar 28 |
19 |
Optimization I: Linear Programming |
[DPV7,ErH] |
| Mar 30 |
20 |
Optimization II: Duality |
[DPV7,ErH] |
| Apr 4 |
21 |
Optimization III: Gradient descent |
[CLRS33,BV9] |
| Apr 6 |
22 |
Intractability: NP-Completeness, reductions |
[DPV8,Er12] |
| Apr 11 |
23 |
Intractability: NP-Complete problems |
[DPV8,Er12] |
| Apr 13 |
Exam |
Midterm II (Lectures 13-21) |
|
| Apr 18 |
24 |
Data Structure II: Hashing |
[ErApp5] |
| Apr 20 |
25 |
Large Scale Computing I: Sketching & streaming |
[CY3] |
| Apr 25 |
26 |
Large Scale Computing II: Parallel & Distributed algorithms |
[CLRS27] |
| May 3 |
Exam |
Final Exam: 9:00am-12:00pm (All lectures) |
|
