(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.1-4.2
  F,09/06 Recurrences
Slides PDF		 CLRS 4.3-4.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
Matrix-chain 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 Bellman-Ford: 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 Mid-term Discussion  
  F,10/18 Network flow
Slides PDF		 CLRS 26.1
HW6 in, HW7 out
due 10/25/2019
9 M,10/21 Max-flow min-cut theorem
Slides PDF		 CLRS 26.2
  W,10/23 Ford-Fulkerson 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 Max-flow
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 Mid-term [PDF,TEX], due XX/XX/2019.
  • Take-home Mid-term [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].