Analysis of Algorithms : An Active Learning Approach

9.3 DYNAMIC PROGRAMMING 257

end if

end for k

costi,loc = tempCost

tracei,loc = tempTrace

end for j

end for i

Once the trace array has been calculated, the following recursive algo-

rithm will use it to determine the actual order for the multiplication. This

algorithm uses a global variable called position that is initialized to 1 and

will keep its value as it is being changed during the recursive calls.

GetOrder( first, last, order )

first the starting matrix location

last the ending matrix location

order the order of matrix multiplication

if first < last then

middle = tracefirst,last

GetOrder( first, middle, order )

GetOrder( middle, last, order )

orderposition = middle

position = position + 1

end if

If you use these two algorithms with the matrix sizes of the last example,

you will get a multiplication order of 2, 1, and 3, which represents doing the

second multiplication first, followed by the first multiplication, and finishing

with the third multiplication. This is the same result shown in Fig. 9.7.

9.3.3

1. Use the matrix multiplication algorithms in Section 9.3.2 to determine the
   most efficient order to multiply the matrices in each of the four following
   cases:
   a.M 1 is 3  5, M 2 is 5  2, M 3 is 2  1, and M 4 is 1  10.
   b.M 1 is 2  7, M 2 is 7  3, M 3 is 3  6, and M 4 is 6  10.
   c.M 1 is 10  3, M 2 is 3  15, M 3 is 15  12, M 4 is 12  7, and M 5 is 7  2.
   d.M 1 is 7  2, M 2 is 2  4, M 3 is 4  15, M 4 is 15  20, and M 5 is 20  5.

■9.3.3 EXERCISES