| 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
| 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
|
CS520: Analysis of Algorithms
