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