. (10) For the chained matrix multiplication problem where we are supposed to fi

Question

. (10) For the chained matrix multiplication problem where we are supposed to find an optimal order by which to calculate M = M1 × M2 × ··· × Mn, we know that we can use the technique of dynamic programming to solve the problem. For each of the following suggested greedy ideas, provide a counter example where the greedy solution does not work:

a) First multiply the matrices Mi and Mi+1 that minimize the product ri1riri+1, and continue in the same way;
b) First multiply the matrices Mi and Mi+1 that maximize the product ri1riri+1, and continue in the same way.

Explanation / Answer

1)

let us take three matrices

A=3x2

B=2x3

C=3x4

according to the given strategy first we have to multiply A,B

then we have to multiply the result with C

cost = cost to multiply A,B + cost to multiply result with C

= 3*2*3 + 3*3*4 = 54

optimal way = multiplyB,C and the multiply A, with result

cost = cost to multiply B,C + cost to multiply A with result

= 2*3*4 + 3*2*4 = 48

2)

let us take three matrices

A=1x10

B=10x2

C=2x10

according to the given strategy , first multiplyB,C and the multiply A, with result

cost = cost to multiply B,C + cost to multiply A with result

= 10*2*10 + 1*10*10 = 300

optimal way = we have to multiply A,B then we have to multiply the result with C

cost = cost to multiply A,B + cost to multiply result with C

= 1*10*2 + 1*2*10 = 40

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.