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
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
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
(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
(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.