Date 
Topic 
Videos discussed 
Reading 
Jan 6 
Administrivia,
Introduction,
Stable Matching 

Chapter 1 in [KT], Chapter 12 here 

Mergesort, Intro divide and conquer 
I. Introduction (Week 1) 
Sections 0.3, 2.12.3 in [DPV], Section 5.1 in [KT] 
Jan 13 
Asymptotic analysis 
II. Asymptotic Analysis (week 1)
III. Divide & Conquer Algorithms (Week I) [First two segments] 
Section 2.2, 2.5 in [DPV]
Sections 2.12.2, 5.15.3, 5.5 in [KT] 
Jan 15 
More on divide and conquer
Inversions
and Matrix multiplication

III. Divide & Conquer Algorithms (Week I) [Strassen's Subcubic Matrix Multiplication Method];
IX. Graphs and the Contraction Algorithm (Week 3) [First two segments]
X. Graph Search and Connectivity (Week 4) [First two segments] 
Counting inversions 
Jan 20 
Discussion of HW1 


Jan 22 
Graph search and connectivity 
X. Graph Search and Connectivity (Week 4) 
Chapter 3, 4.14.2 in [DPV]
Chapter 3 in [KT] 
Jan 27 
Basic graph algorithms continued 


Jan 29 
Graph algorithms continued 


Feb 3 
Greedy algorithms 
III. Introduction to Greedy Algorithms (Week 1) and IV. A Scheduling Application (Week 1) 
Sections 4.14.4 in [KT] 
Feb 5 
Greedy continued 
V. Prim's MST Algorithm (Week 1) and VI. Kruskal's MST Algorithm (Week 2) 
Sections 4.54.7 in [KT], 5.1 in [DPV] 
Feb 10 
Minimum spanning tree algorithms, Application to Clustering 
VII. Clustering (Week 2) 

Feb 12 
Midterm 


Feb 17 
Huffman codes 
IX. Huffman Codes (Week 2) 
Section 5.2 in [DPV], 4.8 in [KT] 
Feb 19 
Dynamic programming I 
X. Introduction to Dynamic Programming (Week 3) 
Chapter 6 in [DPV], Section 6.16.2 in [KT] 
Feb 24 
Dynamic programming II 
XI. The Knapsack Problem (Week 3) and XII. Sequence Alignment 
Sections 6.46.6 in [KT] 
Feb 26 
Additional DP examples 

Problems 6.2 and 6.7 in [DPV] 
Mar 2 
All Pairs Shortest Paths 
XV. Allpairs shortest paths 

Mar 4 
Bellman Ford

XIV. The BellmanFord Algorithm (Week 4) 
Sections 6.86.10 in [KT] 
Mar 9 
NPcompleteness 
XVI. NPcomplete Problems (Week 5) 
Chapter 8 in [DPV] 
Mar 11 
Fun 


Mar 16 
Final 8:30  10:20am
In PCAR 192 

