A classmate suggests the following greedy strategy for the Matrix Chain Multipli

Question

A classmate suggests the following greedy strategy for the Matrix Chain Multiplication problem (see Lecture 10): always multiply the adjacent pair with the maximum shared dimension (break ties arbitrarily). For example, if we are given matrices A_1, A_2, and A_3, with dimensions 10 times 100, 100 times 5, and 5 times 50, this would suggest first multiplying A_1 and A_2, since their shared dimension is 100, while the shared dimension of A_2 and A_3 is only 5. This is the optimal solution for this particular example. Either prove that this always results in an optimal solution, or give a counter-example where there is a better multiplication order than the one given by this strategy.

Explanation / Answer

Counter Example : 2x100 100x10 10x3
A1 A2 A3 with dimensions 2x100 100x10 10x3
As per algorithm , (A1*A2)*A3 as shared dimension of A1 and A2 is 100 which is highest.
2*100*100*10 = 200000
2*10*10*3 = 600
Total = 200600

But the optimal is (A1*(A2*A3))
100*10*10*3 = 30000
2*100*100*3 = 60000
Total = 90000

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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