Homework 1. Reading: Notes for week 1 (product graphs and hypercube symmetries)
Homework 2. Reading: Section 8.1 to 8.4 of Parallel Computation notes. Bisection Width Lower bounds
Homework 3. Reading: All of chapter 10 except for "Normal Algorithms", and section 11.7 of Parallel Computation notes.
Bisection width of the butterfly and related networks.
Homework 4. Reading: Notes on Multibutterflies. , Notes on Probabilistic Method..
Homework 5. Reading: relevant sections of Kleinberg Tardos, chapter 7.
Edmonds Karp Max flow algorithm
Homework 6. Reading: Notes on matching
Matrix multiplication and graphs
Random Walks on undirected graphs
Homework 8. Reading: Geometry of Graphs