(Winter 2021) CS 584/684  Algorithm Design & Analysis
Schedule (subject to change)
General guideline
 Zoom link for lectures, TR 16:40  18:15.
 Zoom link for office hours, F 8:30  10 am. Contact instructor to arrange additional meetings.
Schedule (subject to change)
Week  Date  Topic  Reading & Note 

1  T,01/05  Intro Growth of functions LaTeX tutorial Slides PDF Recording 
CLRS 1  3 Overleaf tutorial 
Th,01/07  Merge sort, Divide&Conquer Slides PDF Recording 
CLRS 2.3,4.1,4.2  
2  T,01/12  Recurrence Slides PDF Recording 
CLRS 4.34.5 
Th,01/14  Elementary graph algorithms Slides PDF Recording 
CLRS 22.1,22.3,10.1  
3  T,01/19  Connected components DAG and topological sort Slides PDF Recording 
CLRS 22.4,22.5 
Th,01/21  Shortest/longest path in DAGs Dynamic programming Slides PDF Recording 
CLRS 15.3 DPV 6.2 PDF 

4  T,01/26  Fibonacci sequence Weighted interval scheduling Slides PDF Recording I II 
KT 6.1 PDF CLRS 15.4 
Th,01/28  Longest common subsequence BellmanFord: shortest path Slides PDF Recording 
CLRS 24.1,24.2  
5  T,02/02  Recitation by TA Recording 

Th,02/04  BellmanFord cont’d Dijkstra’s algorithm Slides PDF Recording 
CLRS 24.3,16.1,16.2  
6  T,02/09  Interval schedule/partition Minimum Spanning Trees Slides: PDF Recording 
CLRS 23,6 
Th,02/11  MST cont’d PDF Recording 
CLRS 21.1,21.2  
7  T,02/16  Amortized analysis Network flow Maxflow mincut theorem Slides PDF 
CLRS 26.1,26.2 
Th,02/18  FordFulkerson algorithm Slides PDF Recording 
CLRS 26.2  
8  T,02/23  Bipartite matching Linear programming Slides PDF Recording 
CLRS 26.3,29 
Th,02/25  Linear programmming cont’d Computational complexity Slides PDF Recording 
CLRS 34 Aaronson big numbers 

9  T,03/02  Reductions, P,NP Slides PDF Recording 
CLRS 34.3 
Th,03/04  NPC Slides PDF Recording 
CLRS 34.4,34.5  
10  T,03/09  Approximation algorithms Randomized algorithms Slides PDF Recording 
CLRS 35.4,C.2,5.2,5.3 Notes by Panigrahi PDF KT 7.1 PDF 
Th,03/11  Final review Selected topic Slides PDF Recording 

11  Final  Takehome exam 
Assignments
Earn extra credit by typing in LaTeX. See Resource for LaTeX tutorials. Submit on Google Classroom (Class code: 5hgfg2p).
 Homework 7 [PDF,TEX], due 4:40pm, 03/11/21.
 Homework 6 [PDF,TEX], due 4:40pm, 03/02/21.
 Homework 5 [PDF,TEX], due 4:40pm, 02/16/21.
 Midterm exam (takehome). Find on Google Classroom. No HW in Week 5.
 Homework 4 [PDF,TEX], due 4:40pm, 02/02/21.
 Homework 3 [PDF,TEX], due 4:40pm, 01/26/21.
 Homework 2 [PDF,TEX], due 4:40pm, 01/19/21.
 Homework 1 [PDF,TEX], due 4:40pm, 01/12/21.