COMP-360B              Assignment 2           Due: February 14, 2003 5pm

Assignments received by Monday 9am get 10% penalty, then 10% per day

last update: Feb 13, 2003 (additional note for question 2)
Assignments are to be left in the box near the labs, McConnell 1st floor.
Late assignments  -10% per day, including weekends.
If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.

1. (Matrix chain multiplication) Study the non-recursive version of matrix chain multiplication (pp 335-7) and the example in Figure 15.3. Then compute similar m and s tables for multiplying five matrices with dimensions 5 x 2, 2 x 6, 6 x 3,  3 x 4 and 4 x 2.

2. Use dynamic programming to solve the following problem. You are given a set S of  n positive integers a1, a2, ... , an and you have to decide if the integers can be partitioned into two subsets with the same total sum. Eg. 7, 11, 3, 6, 5 can be partitioned into subsets 7,3,6 and 11,5 each with sum 16. Your algorithm should output one of the two subsets when the partion is possible.
Hint: The method to use is very similar to one of the problems considered in class.
(A partion of a set S into subsets A and B, means that A and B have empty intersection and their union is S).

3. (Bellman-Ford - see  Lecture Summaries for January 30)
In class we computed the two dimensional table T(i,v), i=1,...,n-1 (see Bruce's handout) , whereas in the algorithm in the text a one dimensional  table d(v) is continually updated (see text p. 588, lines 2-4). I would like you to compare the behaviour of these two versions of the Bellman-Ford algorithm. Do the following:
(a) give an example to show that T(i,v) is not necessarily the same as d(v) at the end of iteration i of the for loops, for some i<n-1.
(b) prove by induction that at the end of each iteration i=1,...,n-1 of the for loops, T(i,v)>=d(v), for all vertices v.
(c) Since both algorithms are correct, it must be that if there is no negative cycle ,  T(n-1,v)=d(v) for each vertex v. Show by example this is not necessarily the case if there is a negative cycle.
4. Solve the all pairs shortest path problem using Johnson's algorithm for the following network:
w(a,b)=6, w(a,e)=16, w(b,c)=8, w(b,e)=7, w(e,b)= -5, w(e,d)= -4, w(c,d)= -3, w(c,e)= -2
(a) Do iteration 1 (Bellman-Ford) in detail showing the values in the table after each iteration.
(b) Draw the network with the modified costs on the edges.
(c) For each other iteration (Dijkstra) you need only show the shortest path tree computed.
(d) Finally give a table with the shortest path weights for each pair of vertices.

You may use either version of the Bellman-Ford algorithm.