(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.3-4.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
Bellman-Ford: shortest path
Slides PDF Recording
CLRS 24.1,24.2
5 T,02/02 Recitation by TA
Recording
 
  Th,02/04 Bellman-Ford 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
Max-flow min-cut theorem
Slides PDF
CLRS 26.1,26.2
  Th,02/18 Ford-Fulkerson 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
 
11 Final Take-home 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.
  • Mid-term exam (take-home). 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.