Disclaimer: The following schedule lists the major topics which we will cover and the expected due dates for the assignments. This is my best guess on how the course will proceed.
(Last Updated: 03/31/09 )
| Week | Topics | Due |
| 1. Tuesday Mar 31 | Graph Definitions | |
| 1. Thursday Apr 2 | Trees, Number of Trees, Isomorphisms, Euler Tours | Hw 1 assigned |
| 2. Tuesday Apr 7 | Hamiltonian Graphs, Planarity and Euler`s Formula | |
| 2. Thursday Apr 9 | Planarity (continued), Directed Graphs, Euler Tours | Hw1 due |
| 3. Tuesday Apr 14 | Orientable graphs, Representations, BFS, Bipartite, DFS, Topological Sorts | Hw2 assigned |
| 3. Thursday Apr 16 | Incidence Matrix, Matrix Tree Theorem | |
| 4. Tuesday Apr 21 | Number of arborescences, Matrix Tree and Cayley's Theorems | Hw 2 due Hw 3 assigned |
| 4. Thursday Apr 23 | Number of Euler Tours, LaPlacian, Google Matrix, Steiner Trees | |
| 5. Tuesday Apr 28 | Matroids | Hw 3 due Hw 4 assigned |
| 5. Thursday Apr 30 | Network Flow | |
| 6. Tuesday May 5 | Flow algorithms, Edmonds-Karp proof | |
| 6. Thursday May 7 | Layered Networks, Dinic's algorithm |
Hw 4 due |
| 7. Tuesday May 12 | Bound on number of phases, MKM algorithm for blocking flows | |
| 7. Thursday May 14 | Midterm | |
| 8. Tuesday May 19 | 0-1 Flows, Menger's Theorems | Hw 5 assigned |
| 8. Thursday May 21 | Vertex and edge connectivity | |
| 9. Tuesday May 26 | Matchings, bipartite matchings, Edmonds algorithm | |
| 9. Thursday May 28 | Edmonds (continued) | Hw 5 due |
| 10. Tuesday Jun 2 | Feasible circulations and min-cost applications | Hw 6 assigned |
| 10. Thursday Jun 4 | overflow | |
| Friday Jun 5 | Hw 6 due | |
| Monday Jun 8 | FINAL EXAM 4-7pm |
Portions of the CMPE277 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited.
Comments to: martine@cse.ucsc .edu (Last Update: 03/31/09 )