| Week |
Dates |
Topics |
Material |
Due |
| 1 |
1/22-1/25
| Overview, Network Flow
| Cormen, 26.1, 26.2
|
|
| 2 |
1/28-2/1
| Splay trees, linking-and-cutting trees
| Handout, Chapters 4 and 5
|
|
| 3 |
2/4-2/8
| Linking/cutting trees; network flow.
| Tarjan, Chapter 8.
Review Cormen 22.1-22.4. Here's a study
guide
| Homework 1
|
| 4 |
2/11-2/15
| Finish linking/cutting trees; network flow; matching
| Tarjan, Chapter 8, Chapter 9. Morgan e-Reserve has posted Chapter 9.
|
|
| 5 |
2/28-2/22
| Matching
| Tarjan, Chapter 9. Morgan e-Reserve has posted it.
|
|
| 6 |
2/25-3/1
| Matching; improvements to Edmonds's bound. Union-find ADT.
| Tarjan, Chapter 9, Cormen, Chapter 21.1-21.3 -- familiarize yourself with the ADT
(21.1) before the lecture on 2/26, since it is used to get the new bounds for
matching.
| Homework 2, due 2/26
|
| 7 |
3/4-3/8
| Finish matching, All-pairs shortest paths
| Cormen, Chapter 25, especially 25.3.
| Homework 3, due 3/14
|
| 8 |
3/11-3/15
| All-pairs shortest paths
|
|
|
|
3/18-3/22
| Spring break -- have fun
|
|
|
| 9 |
3/25-3/29
| Review for midterm; clinic on reading journal papers and monographs in our field.
| Study guide for midterm
|
|
| 10 |
4/1-4/5
| Midterm Tuesday. Computational geometry
| Handout from 3/26.
|
|
| 11 |
4/8-4/12
| Sweep-line algorithm for line-segment intersections, and applications
| Handout from 3/26, Chapter 2.
|
|
| 12 |
4/15-4/19
| Orthogonal range searching.
| M. de Berg et. al., Computation Geometry: Algorithms and Applications, Chapter 5. Log into
your CSU library account and search for the eBook version. You can download chapters individually.
| Homework 4
|
| 13 |
4/22-4/25
| Orthogonal range searching; Point location
| M. de Berg et. al., Chapter 6
|
|
| 14 |
4/22-4/25
| Point location; Voronoi diagrams
| M. de Berg et. al., Chapters 6 and 7
| Homework 5
Homework 5 solution
|
Final exam: May 14, 6:20-8:20
CS520: Analysis of Algorithms
