CSC 477/677 Assignment 4

Fall 2004

Due March 25, 2004

• Work problems 5.1 and 5.2 on page 181 of your textbook, using a programming language of your choice. The problem will not be graded, so do not hand it in.
• Work problems 5.6 on page 181 of your textbook.
• Work problem 5.14 on page 182 of your textbook. (This problem is hard.)
• Work problem 5.18 on page 183 of your textbook. (This problem is easy.)
• This problem is postponed to the next homework. Work problem 5.32 on page 185 of your textbook.
• Work problem 6.10 on page 215 of your textbook.
• Work problem 6.15 on page 216 of your textbook.
• This problem is postponed to the next homework. Work Floyd's algorithm (on page 269 of your textbook) by hand to solve the all-pairs minimum path problem for the weighted directed graph G, illustrated below. I realize that different browsers have different capabilities. Therefore:

  eps version of G. (Use ghostview.)

  pdf version of G. (Use acrobat. If that doesn't work directly, then right-click on this link and copy to your desktop, then left-click on the new icon, which should automatically call acrobat if you have it.)

  fig version of G. (Make a copy, then use xfig.)

  postscript version of G. (Use ghostview.)

  dvi version of G. (Make a copy, then use xdvi or dvips.)

  These are all the same, so you only need to be able to read one of them.