MA618 Homework #4
Due Monday, March 1

Problems to turn in

1. 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.
2. Problem (Minimum-weight dipaths in graphs with no dicycles) p.29. Include a proof that the bijection exists.
3. Problem (Knapsack program) p.29. Do part (a) only.
4. Exercise (Scheduling, continued) p.42.
5. Exercise (Intersection of three matroid polytopes) p.46.

Problems to do but not to turn in

1. Exercise (Bellman-Ford Algorithm) p.25.
2. Exercise (Dijkstra's Algorithm) p.27.
3. Exercise (Shortcut) p.38.

• About this document ...