| 1 |
M 8/28 |
L01 |
Introduction |
[Er0] |
|
|
| W 8/30 |
L02 |
Divide & Conquer I: Recursion and Mergesort |
[DPV2,Er1] |
HW 1 (Preq) |
|
| F 9/1 |
R01 |
Prerequisites |
|
|
|
| 2 |
M 9/4 |
|
LABOR DAY - NO MEETING |
|
|
|
| W 9/6 |
L03 |
Divide & Conquer II: Randomized Quicksort |
[Er1,Ed2] |
HW 2 (Divide & Conquer) |
|
| Th 9/7 |
|
|
|
|
HW 1 |
| F 9/8 |
R02 |
Divide and Conquer |
|
|
|
| 3 |
M 9/11 |
L04 |
Divide & Conquer III: Selection |
[DPV2,Er1] |
|
|
| W 9/13 |
L05 |
Parallel Algorithms I: Concepts and Analysis |
[CLRS27] |
HW3 (Parallel Algorithms) |
|
| Th 9/14 |
|
|
|
|
HW 2 |
| F 9/15 |
R03 |
Divide & Conquer and Parallel Algorithms |
|
|
|
| 4 |
M 9/18 |
L06 |
Parallel Algorithms II: Algorithm Design |
[CLRS27] |
|
|
| W 9/20 |
L07 |
Dynamic Programming I: Introduction,Sequence Alignment |
[DPV6,Er3] |
HW 4(dynamic programming) |
|
| Th 9/21 |
|
|
|
|
HW 3 |
| F 9/22 |
R04 |
Parallel Algorithms and Dynamic Programming |
|
|
|
| 5 |
M 9/25 |
L08 |
Dynamic Programming II: Knapsack, Chain Matrix |
[DPV6,Er3] |
|
|
| W 9/27 |
L09 |
Graph Traversal I: Depth-First Search, Topological Sort |
[DPV3,Er6] |
HW 5 (DP & DFS) |
|
| Th 9/28 |
|
|
|
|
HW 4 |
| F 9/29 |
R05 |
Dynamic Programming and Graph Traversal |
|
|
|
| 6 |
M 10/2 |
L10 |
Graph Traversal II: Breadth-First Search |
[DPV4,Er5] |
|
|
| W 10/4 |
L11 |
Shortest Paths I: Dijkstra's Algorithm |
[DPV4,Er8] |
HW 6 (Shortest Paths) |
|
| Th 10/5 |
|
|
|
|
HW 5 |
| F 10/6 |
R06 |
Graph Traversal II: Breadth-First Search and Shortest Paths I: Dijkstra's Algorithm |
|
|
|
| 7 |
M 10/9 |
L12 |
Shortest Paths II: A*, Bellman-Ford, Floyd Warshall |
[DPV4,Er8,9] |
|
|
| W 10/11 |
L13 |
Greedy I: Scheduling and Compression |
|
|
|
| Th 10/12 |
|
|
|
|
HW 6 |
| F 10/13 |
R07 |
Shortest Paths II: A*, Bellman-Ford, Floyd Warshall |
|
|
|
| 8 |
M 10/16 |
|
FALL BREAK - NO MEETING |
|
|
|
| W 10/18 |
L14 |
Industry guest speaker(s) |
[DPV5,Er4] |
|
|
| F 10/20 |
R08 |
Exam Review |
|
|
|
| 9 |
M 10/23 |
L15 |
MIDTERM EXAM (Lectures 1-12) |
|
Case Study |
|
| W 10/25 |
L16 |
Greedy II: Minimum Spanning Tree |
[DPV5,Er7] |
HW 7 (Greedy Algorithms) |
|
| F 10/27 |
R09 |
Greedy Algorithms |
|
|
|
| 10 |
M 10/30 |
L17 |
Cuts and Flows I: Max-flow and Min-cut |
[Er10] |
|
|
| W 11/1 |
L18 |
Cuts & Flows II: Computing flows |
[Er10] |
HW 8 (Cuts and Flows) |
|
| Th 11/2 |
|
|
|
|
HW 7 |
| F 11/3 |
R10 |
Cuts and Flows |
|
|
|
| 11 |
M 11/6 |
L19 |
Hardness I: Complexity Classes and NP-Completeness |
[DPV8,Er12] |
|
|
| W 11/8 |
L20 |
Hardness II: NP-Complete Problems and Reductions |
[DPV8,Er12] |
HW 9 (Hardness) |
|
| Th 11/9 |
|
|
|
|
HW 8 |
| F 11/10 |
R11 |
Hardness |
|
|
|
| 12 |
M 11/13 |
L21 |
Hardness III: More reductions and implications |
[DPV8,Er12] |
|
|
| W 11/15 |
L22 |
Approximation: Greedy scheduling, Traveling Salesperson |
DPV9.2, ErAppJ |
|
|
| Th 11/16 |
|
|
|
|
HW 9 |
| F 11/17 |
R12 |
Hardness and Approximation |
|
|
|
| 13 |
M 11/20 |
L23 |
Big Data 1: Clustering-Greedy |
[CLRS33,Ph8] |
HW 10 (More Hardness, Big Data) |
|
| Tu 11/21 |
|
|
|
|
Case Study |
| W 11/22 |
|
THANKSGIVING BREAK - NO MEETING |
|
|
|
| F 11/24 |
|
THANKSGIVING BREAK - NO MEETING |
|
|
|
| 14 |
M 11/27 |
L24 |
Big Data 2: Clustering-kmeans and randomized |
[CLRS33,Ph8] |
|
|
| W 11/29 |
L25 |
Big Data 3: Hashing |
[ErApp5] |
|
|
| F 12/1 |
R13 |
Big Data |
|
|
|
| 15 |
M 12/4 |
L26 |
Big Data 4: Sketching |
[CY3] |
|
HW10 |
| W 12/6 |
L27 |
LATE-TERM EXAM (L14-25) |
|
|
|
| F 12/8 |
R14 |
|
|
|
|
| 16 |
M 12/11 |
|
NO MEETING, READING PERIOD |
|
|
|
| W 12/13 |
|
EXAM PERIOD |
|
|
|
| Th 12/14 |
|
FINAL EXAM 2-5 pm |
|
|
|
