next up previous
Next: About this document

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 tex2html_wrap_inline16 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 tex2html_wrap_inline22 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.

Carl Lee
Mon Feb 22 07:50:33 EST 1999