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: DepthFirst Search, Topological Sort 
[DPV3,Er6] 
M 10/2 
10 
Graph Traversal II: BreadthFirst Search 
[DPV4,Er5] 
W 10/4 
11 
Shortest Paths I: Dijkstra's Algorithm 
[DPV4,Er8] 
M 10/9 
12 
Shortest Paths II: A*, BellmanFord, 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 112) 

W 10/25 
16 
Greedy II: Minimum Spanning Tree 
[DPV5,Er7] 
M 10/30 
17 
Cuts and Flows I: Maxflow and Mincut 
[Er10] 
W 11/1 
18 
Cuts & Flows II: Computing flows 
[Er10] 
M 11/6 
19 
Hardness I: Complexity Classes and NPCompleteness 
[DPV8,Er12] 
W 11/8 
20 
Hardness II: NPComplete 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: ClusteringGreedy 
[CLRS33,Ph8] 
M 11/27 
24 
Big Data 2: Clusteringkmeans 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 
LATETERM EXAM (L1425) 
[CLRS27] 
Th 12/14 
Exam 
FINAL EXAM 25 pm (All lectures) 
