(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 Recording |
||
| 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.