Next: About this document
MA618 Homework #4
Due Monday, March 1
Problems to turn in
Problems to do but not to turn in
- Problem (Recovering the dipaths with the Floyd-Warshall
Algorithm) p.26. Suggestion: Assume the vertices are numbered from
1 to n=|V(G)|. Keep an extra
matrix around, initially filled with 0's.
Whenever the minimum in step 2 is changed to a new value,
change entry (v,w) to k.
- Problem (Minimum-weight dipaths in graphs with no dicycles)
p.29. Include a proof that the bijection exists.
- Problem (Knapsack program) p.29. Do part (a) only.
- Exercise (Scheduling, continued) p.42.
- Exercise (Intersection of three matroid polytopes) p.46.
- Exercise (Bellman-Ford Algorithm) p.25.
- Exercise (Dijkstra's Algorithm) p.27.
- Exercise (Shortcut) p.38.
Mon Feb 22 07:50:33 EST 1999