(Fall 2019) CSCE 629  Analysis of Algorithms
Schedule (subject to change)
Week  Date  Topic  Reading & Note 

1  M,08/26  Intro Growth of functions Intro slides PDF 
DLRS 1  3 
W,08/28  LaTeX tutorial (by Andrew Nemec)  Overleaf tutorial  
F,08/30  Cancelled due to QCrypt’19  HW1 out (see below) due 09/06/2019 

2  M,09/02  (Labor day) Merge sort Slides PDF 
CLRS 2.3 
W,09/04  Divide&Conquer Slides PDF 
CLRS 4.14.2  
F,09/06  Recurrences Slides PDF 
CLRS 4.34.5 HW1 due, HW2 out due 09/13/2019 

3  M,09/09  Recitation by TA  
W,09/11  Graph basics Guest lecturer: Prof. Andreas Klappenecker Slides PDF 
CLRS 22.1,22.2  
F,09/13  Graph traversal and applications Slides PDF 
CLRS 22.3,10.4 HW2 due, HW3 out due 09/20/2019 

4  M,09/16  Connected components Slides PDF 
CLRS 10.1,22.5 
W,09/18  DAG and topological sort Slides PDF 
CLRS 22.4  
F,09/20  Dynamic Programming Slides PDF 
CLRS 15 HW3 due, HW4 out due 09/27/2019 

5  M,09/23  Fibonacci Weighted interval scheduling Slides PDF 
KT 6.1 PDF 
W,09/25  Elements of DP Matrixchain multiplication Slides PDF 
CLRS 15.2,15.3  
F,09/27  Longest common subsequence Slides PDF 
CLRS 15.4 HW4 due, HW5 out due 10/04/19 

6  M,09/30  Recitation by TA  
W,10/02  BellmanFord: shortest path Slides PDF 
CLRS 24.1,24.2  
F,10/04  Dijkstra’s algorithm Greedy algorithm Slides PDF 
CLRS 24.3,16 HW5 in 

7  M,10/07  Greedy algorithm Interval schedule/partition Slides PDF 
CLRS 16.1,16.2 HW6 out due 10/18/19 
W,10/09  Minimum Spanning Trees Slides PDF 
CLRS 23  
F,10/11  MST Slides PDF 
CLRS 23  
8  M,10/14  Data structure Amortized analysis Slides PDF 
CLRS 6,21.1,21.2 
W,10/16  Midterm Discussion  
F,10/18  Network flow Slides PDF 
CLRS 26.1 HW6 in, HW7 out due 10/25/2019 

9  M,10/21  Maxflow mincut theorem Slides PDF 
CLRS 26.2 
W,10/23  FordFulkerson algorithm Guest lecture by Prof. Klappenecker Slides PDF 
CLRS 26.2  
F,10/25  Bipartite matching Guest lecture by Prof. Klappenecker Slides PDF 
CLRS 26.3 HW7 in, HW8 out due 11/01/2019 

10  M,10/28  Recitation by TA  
W,10/30  More on Maxflow Linear programming Slides PDF 
CLRS 29  
F,11/01  Linear Programming Slides PDF 
CLRS 29 HW8 in, HW9 out due 11/08/2019 

11  M,11/04  Computational intractability intro Slides PDF 
CLRS 34 Aaronson big numbers 
W,11/06  Reductions Slides PDF 
CLRS 34  
F,11/08  P, NP Slides PDF 
CLRS 34 HW9 in, HW10 out due 11/15/2019 

12  M,11/11  NPC Slides PDF 
CLRS 34 
W,11/13  NPC cont’d Slides PDF 
CLRS 34  
F,11/15  Hamiltonian cycle Approximation algorithms Slides PDF 
KT 8.5 PDF CLRS 35.1 HW10 in, HW11 out due 11/22/2019 

13  M,11/18  (Bonfire remeberance) Approximation algorithms LP rexlaxation Slides PDF 
CLRS 35.4 Notes by Panigrahi PDF 
W,11/20  Randomized algorithms Slides PDF 
KT 7.1 PDF CLRS C.2,5.2,5.3 

F,11/22  Randomized algorithms cont’d Slides PDF 
CLRS 7.2 Notes by Panigrahi PDF HW11 in, HW12 out due 12/02/2019 

14  M,11/25  Final Review Slides PDF 

W,11/27  Reading day  
F,11/29  Thanksgiving holiday  
15  M,12/02  (Redefined Friday) Quantum computing 
Cleve’s slides PDF Aaronson’s note link HW12 in 
W,12/04  Quantum computing  Cleve’s slides PDF Aaronson’s note link Nielsen’s videos link 

16  T,12/10  Final Exam 8 am  10 am 
Assignments
You solutions must be typed in LaTeX. See Resource for LaTeX tutorials. Submit on Gradescope (Entry code: 96XG2X).
 Homework 1 [PDF,TEX], due 10am, 09/06/2019.
 Homework 2 [PDF,TEX], due 10am, 09/13/2019.
 Homework 3 [PDF,TEX], due 10am, 09/20/2019.
 Homework 4 [PDF,TEX], due 10am, 09/27/2019.
 Homework 5 [PDF,TEX], due 10am, 10/04/2019.
 Homework 6 [PDF,TEX], due 10am, 10/18/2019.
 Practice Midterm [PDF,TEX], due XX/XX/2019.
 Takehome Midterm [PDF,TEX], due 10am, 10/14/2019.
 Homework 7 [PDF,TEX], due 10am, 10/25/2019.
 Homework 8 [PDF,TEX], due 10am, 11/01/2019.
 Homework 9 [PDF,TEX], due 10am, 11/08/2019.
 Homework 10 [PDF,TEX], due 10am, 11/15/2019.
 Homework 11 [PDF,TEX], due 10am, 11/22/2019.
 Homework 12 [PDF,TEX], due 10am, 12/02/2019.
 Practice Final Exam [PDF,TEX].