| Date |
Lecture |
Topic |
Reference |
| M 8/28 |
1 |
Introduction |
[Er0] |
| W 8/30 |
2 |
Divide & Conquer I: Recursion and Mergesort |
[DPV2,Er1] |
| W 9/6 |
3 |
Divide & Conquer II: Randomized Quicksort |
[Er1, Ed2] |
| M 9/11 |
4 |
Divide & Conquer III: Selection |
[DPV2,Er1] |
| W 9/13 |
5 |
Parallel Algorithms I: Concepts and Analysis |
[CLRS27] |
| M 9/18 |
6 |
Parallel Algorithms II: Algorithm Design |
[CLRS27] |
| W 9/20 |
7 |
Dynamic Programming I: Introduction,Sequence Alignment |
[DPV6,Er3] |
| M 9/25 |
8 |
Dynamic Programming II: Knapsack, Chain Matrix |
[DPV6,Er3] |
| W 9/27 |
9 |
Graph Traversal I: Depth-First Search, Topological Sort |
[DPV3,Er6] |
| M 10/2 |
10 |
Graph Traversal II: Breadth-First Search |
[DPV4,Er5] |
| W 10/4 |
11 |
Shortest Paths I: Dijkstra's Algorithm |
[DPV4,Er8] |
| M 10/9 |
12 |
Shortest Paths II: A*, Bellman-Ford, Floyd Warshall |
[DPV4,Er8,9] |
| W 10/11 |
13 |
Greedy I: Scheduling and Compression |
|
| W 10/18 |
14 |
Industry guest speaker(s) |
[DPV5,Er4] |
| M 10/23 |
15 |
MIDTERM EXAM (Lectures 1-12) |
|
| W 10/25 |
16 |
Greedy II: Minimum Spanning Tree |
[DPV5,Er7] |
| M 10/30 |
17 |
Cuts and Flows I: Max-flow and Min-cut |
[Er10] |
| W 11/1 |
18 |
Cuts & Flows II: Computing flows |
[Er10] |
| M 11/6 |
19 |
Hardness I: Complexity Classes and NP-Completeness |
[DPV8,Er12] |
| W 11/8 |
20 |
Hardness II: NP-Complete Problems and Reductions |
[DPV8,Er12] |
| M 11/13 |
21 |
Hardness III: More reductions and implications |
[DPV8,Er12] |
| W 11/15 |
22 |
Approximation: Greedy scheduling, Traveling Salesperson |
TBA |
| M 11/20 |
23 |
Big Data 1: Clustering-Greedy |
[CLRS33,Ph8] |
| M 11/27 |
24 |
Big Data 2: Clustering-kmeans and randomized |
[CLRS33,Ph8] |
| W 11/29 |
25 |
Big Data 3: Hashing |
[ErApp5] |
| M 12/4 |
26 |
Big Data 4: Sketching |
[CY3] |
| W 12/6 |
27 |
LATE-TERM EXAM (L14-25) |
[CLRS27] |
| Th 12/14 |
Exam |
FINAL EXAM 2-5 pm (All lectures) |
|
