Four Matrices \(M_1 , M_2, M_3\) and \(M_4\) of dimensions \(p \times q, \ q…
2011
Four Matrices \(M_1 , M_2, M_3\) and \(M_4\) of dimensions \(p \times q, \ q \times r , \ r \times s\) and \(s \times t\) respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as \(((M_1 \times M_2) \times (M_3 \times M_4))\) the total number of scalar multiplications is \(pqr + rst + prt\). When multiplied as \((((M_1 \times M_2) \times M_3) \times M_4)\), the total number of scalar multiplications is \(pqr + prs + pst\).
If \(p=10, q=100, r=20, s=5\) and \(t=80\), then the minimum number of scalar multiplications needed is
- A. 248000
- B.
44000
- C.
19000
- D.
25000
Attempted by 91 students.
Show answer & explanation
Correct answer: C
Answer: 19000
Explanation and costs for each possible parenthesization:
((M1 x M2) x (M3 x M4)): M1 x M2 = 10 x 100 x 20 = 20000; M3 x M4 = 20 x 5 x 80 = 8000; final multiply = 10 x 20 x 80 = 16000; Total = 20000 + 8000 + 16000 = 44000.
(((M1 x M2) x M3) x M4): M1 x M2 = 20000; (result) x M3 = 10 x 20 x 5 = 1000; (result) x M4 = 10 x 5 x 80 = 4000; Total = 20000 + 1000 + 4000 = 25000.
((M1 x (M2 x M3)) x M4): M2 x M3 = 100 x 20 x 5 = 10000; M1 x (result) = 10 x 100 x 5 = 5000; (result) x M4 = 10 x 5 x 80 = 4000; Total = 10000 + 5000 + 4000 = 19000.
(M1 x ((M2 x M3) x M4)): M2 x M3 = 10000; (result) x M4 = 100 x 5 x 80 = 40000; M1 x (result) = 10 x 100 x 80 = 80000; Total = 10000 + 40000 + 80000 = 130000.
(M1 x (M2 x (M3 x M4))): M3 x M4 = 20 x 5 x 80 = 8000; M2 x (result) = 100 x 20 x 80 = 160000; M1 x (result) = 10 x 100 x 80 = 80000; Total = 8000 + 160000 + 80000 = 248000.
The smallest total cost is 19000, achieved by the parenthesization where M2 and M3 are multiplied first, then M1 multiplies that result, and finally the product multiplies M4.
A video solution is available for this question — log in and enroll to watch it.