Question & Answer: Review the textbook on the matrix chain multiplication problem. Find an optimal parenthesization of…..

Solution:

Using the given matrix-chain <2,6,5,3,4,7>

A1 = 2, 6

A2 = 6, 5

A3 = 5, 3

A4 = 3, 4

A5 = 4, 7

Consider p0=2, p1=6, p2=5, p3=3, p4=4, p5=7

m[1,1] = m[2,2] = m[3,3] = m[4,4] = m[5,5] = 0

Using equation of matrix –chain product from text:

m[i, j] = 0, if i = j,

m[i,j]= {min {m[i,k] + m[k+1, j] + pi –1pkpj}}, if i < j

where k=j-1

step1:

m[1, 2] = m[1, 1] + m[2, 2] + (P0 * P1 * P2) = 0+0+(2*6*5) =60

m[2,3] = m[2, 2] + m[3, 3]+( p1*p2*p3) = 0+0+(6*5*3) = 90

m[3,4] = m[3, 3] + m[4, 4]+(p2*p3*p4)=0+0+(5*3*4 )= 60

m[4,5] =m[4, 4] + m[5, 5] +( p3*p4*p5) =0+0+( 3*4*7) = 84

step 2:

m[1, 3] = m[1, 1] + m[2, 3] + (p0*p1*p3)=0+90+(2*6*3)=90+36=126

m[1, 3] = m[1, 2] + m[3, 3] +(p0*p2*p3)=60+0+(2*5*3)=60 +30 =90

m[2, 4] = m[2, 2] + m[3, 4] +(p1*p2*p4)= 0+60+(6*5*4)=60+120= 180

m[3, 5] = m[3, 4] + m[5, 5] +( p2*p4*p5)= 60+0+(5*4*7)=60+140= 200

step 3:

m[1, 4] = m[1, 2] + m[3, 4] +(p0*p2*p4)=60+60+(2*5*4)= 160

m[2, 5] = m[2, 2] + m[3, 5] + (p1*p2*p5)=0+200+(6*5*7)=410

step 4:

m[1, 5] = m[1, 4] + m[5, 5] + (p0*p4*p5)=160+0+(2*4*7) = 216

here we have taken the minimum value of k for filling m table

Each entry s[i, j] records a value of k such that an optimal parenthesization of AiAi+1…j splits the product between Ak and Ak+1.” Therefore, we get the following s-table:

in this problem n= 5

The array s[1…5, 1…5] has been computed above.

s[1,5] = 2 (A1A2)(A2A3)(A3A4)(A4A5)

s[1,2] = 1 (A1A2)

s[3,5] = 4 (A3A4)(A4A5)

So the final multiplication sequence is (A1A2)(A2A3)(A3A4)(A4A5)