General Information
Course Website: http://www.math.uwaterloo.ca/~harvey/W10/
Lecture Time: Tuesdays
& Thursdays, 11:30am-12:50pm
Lecture Room: RCH 208
Instructor: Professor Nicholas Harvey, MC 6068, harvey@math.uwaterloo.ca
·
Office Hours: Thursdays, 2:00-3:00pm
Teaching
Assistant: David Roberson, DC 3144, droberson@uwaterloo.ca
· Office Hours: Tuesdays, 1:30-2:30pm
Assignments
There will be about 5 assignments in this class. The
questions are handed out in class, and also available below.
|
|
Handed
out |
Due
date |
Questions |
Solutions |
|
1. |
1/14 |
1/21 |
||
|
2. |
1/26 |
2/4 |
||
|
3. |
2/4 |
2/11 |
||
|
4. |
3/2 |
3/11 |
||
|
5. |
3/18 |
3/30 |
Lecture Schedule
|
|
Date |
Topics |
Relevant
Reading |
|
1. |
1/5 |
Course
Overview, Currency Exchange Example, Swiss Bank Example |
Course
Notes Section 2.1 |
|
2. |
1/7 |
Longest
Dipath, Knapsack Problem, Decomposition of Diwalks |
Course
Notes Section 1.2, 2.1.2, 2.2.1 |
|
3. |
1/12 |
Potentials:
Existence & relation to shortest diwalks |
Course
Notes Section 2.2.2 |
|
4. |
1/14 |
Potentials.
A linear program for shortest paths. |
Course
Notes Section 2.2.2, 2.2.3 |
|
5. |
1/19 |
Potentials:
String & nuts example. Dual of the shortest paths LP. |
Course
Notes Section 2.2.3 |
|
6. |
1/21 |
Shortest
path trees. Internet routing example. Dijkstra’s
Algorithm. |
Course
Notes Section 2.2.5, 2.3 |
|
7. |
1/26 |
Directed acyclic
graphs: Topological Sort and Shortest Paths |
Course
Notes Section 2.4.1, 2.4.2 |
|
8. |
1/28 |
Shortest
paths in arbitrary digraphs: the Bellman-Ford Algorithm |
|
|
9. |
2/2 |
Maximum
Flows: Definition, LP, Incrementing Paths |
Course Notes
Section 3, 3.1 |
|
10. |
2/4 |
Residual
Digraph, Ford-Fulkerson Algorithm, Max Flow <= Min Cut |
Course
Notes Section 3.3, 3.2 |
|
11. |
2/9 |
Optimality
conditions, Max Flow = Min Cut, Integral Flows |
Course
Notes Section 3.2, 3.3 |
|
12. |
2/11 |
Bipartite
Matching via Max Flow, Konig’s Theorem |
Course
Notes Section 3.6.3 |
|
13. |
2/23 |
Midterm Exam. Solutions |
|
|
14. |
2/25 |
The
Edmonds-Karp Algorithm |
Course
Notes Section 3.3.1 |
|
15. |
3/2 |
Finish
Edmonds-Karp. Optimal Closures. |
Course
Notes Section 3.3.1, 3.5.3 |
|
16. |
3/4 |
Circulation Decomposition, Flow
Decomposition, Disjoint Dipaths |
Course
Notes Section 3.6.1, 3.6.2 |
|
17. |
3/9 |
Menger’s Theorem, Flows with Lower Bounds |
Course Notes
Section 3.6.2, 3.4 |
|
18. |
3/11 |
Minimum
Cost Flows |
Course
Notes Section 4.1, 4.2 |
|
19. |
3/16 |
Sufficient
conditions for feasible flows, Incrementing cycles |
Course
Notes Section 4.2, 4.3 |
|
20. |
3/18 |
Incrementing
Cycle Algorithm, Optimality Conditions |
Course Notes
Section 4.3, 4.4.3, 4.4.1 |
|
21. |
3/23 |
Optimality
Conditions, Tree Flows |
Course
Notes Section 4.4, 4.5 |
|
22. |
3/25 |
Network
Simplex Method |
Course
Notes Section 4.5 |
|
23. |
3/30 |
Network
Simplex Wrap-up & Example |
Course
Notes Section 4.5 |
|
24. |
4/1 |
Class cancelled |