Analysis of Algorithms : An Active Learning Approach

256 OTHER ALGORITHMIC TECHNIQUES

a matrix called trace that is used by the next algorithm to actually determine

the order of the multiplication that will produce this minimum cost.

for i = 1 to N do

costi,i = 0

end for

for i = 1 to N-1 do

for j = 1 to N-i do

loc = i + j

tempCost = ∞

for k = i to loc-1 do

if tempCost > costi,k + costk+1,loc + si*sk*sloc then

tempCost = costi,k + costk+1,loc + si*sk*sloc

tempTrace = k

Multiplication Order Resulting Matrix Size Total Cost in Multiplications

M 1 ∗ M 2

M 2 ∗ M 3

M 3 ∗ M 4

(M 1 ∗ M 2 )∗ M 3

((M 1 ∗ M 2 )∗ M 3 )∗ M 4

(M 1 ∗ (M 2 ∗ M 3 ))∗ M 4

M 1 ∗ ((M 2 ∗ M 3 )∗ M 4 )

(M 1 ∗ M 2 )∗ (M 3 ∗ M 4 )

M 1 ∗ (M 2 ∗ (M 3 ∗ M 4 ))

(M 2 ∗ M 3 )∗ M 4

M 1 ∗ (M 2 ∗ M 3 )

M 2 ∗ (M 3 ∗ M 4 )

20 × 35

20 × 25

20 × 25

20 × 25

20 × 25

20 × 25

20 × 4

20 × 4

35 × 25

5 × 25

5 × 25

5 × 4

3500

700

3500

3500 + 2800 = 6300

700 + 400 = 1100

700 + 500 = 1200

3500 + 4375 = 7875

6300 + 2000 = 8300

1100 + 2000 = 3100

1200 + 2500 = 3700

7875 + 2500 = 10,375

3500 + 3500 + 17,500 = 24,500

■FIGURE 9.7

The amount of

work needed to

multiply four

matrices in

different orders