Assume that multiplying a matrix \(G_1\) of dimension \(𝑝 × 𝑞\) with another…
2018
Assume that multiplying a matrix \(G_1\) of dimension \(𝑝 × 𝑞\) with another matrix \(G_2\) of dimension \(𝑞 × 𝑟\) requires \(𝑝𝑞𝑟\) scalar multiplications. Computing the product of n matrices \(G_1G_2G_3…G_n\) can be done by parenthesizing in different ways. Define \(G_i G_{i+1}\) as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain \(G_1G_2G_3G_4G_5G_6\) using parenthesization \((G_1(G_2G_3))(G_4(G_5G_6)), G_2G_3\) and \(G_5G_6\) are the only explicitly computed pairs.
Consider a matrix multiplication chain \(F_1F_2F_3F_4F_5\), where matrices \(F_1, F_2, F_3, F_4\) and \(F_5\) are of dimensions \(2×25, 25×3, 3×16, 16×1\) and \(1×1000\), respectively. In the parenthesization of \(F_1F_2F_3F_4F_5\) that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
Answer: C. \(F_3F_4\) only — Key insight: choose the small adjacent product first and use dynamic programming to find the minimal total cost. Matrix dimensions: F1 is 2×25, F2 is 25×3, F3…
- A.
\(F_1F_2\)and\(F_3F_4\)only - B.
\(F_2F_3\)only - C.
\(F_3F_4\)only - D.
\(F_1F_2\)and\(F_4F_5\)only
Attempted by 71 students.
Show answer & explanation
Correct answer: C
Key insight: choose the small adjacent product first and use dynamic programming to find the minimal total cost.
Matrix dimensions: F1 is 2×25, F2 is 25×3, F3 is 3×16, F4 is 16×1, F5 is 1×1000.
Costs for adjacent pair multiplications:
F1×F2: 2×25×3 = 150; F2×F3: 25×3×16 = 1,200; F3×F4: 3×16×1 = 48; F4×F5: 16×1×1000 = 16,000.
Dynamic choices (key steps): compute F3F4 first (cost 48) because it is cheapest; then multiply that by F2 (cost 25×3×1 = 75) to get the product F2(F3F4); then multiply by F1 (cost 2×25×1 = 50) to obtain F1(F2(F3F4)); finally multiply that by F5 (cost 2×1×1000 = 2,000).
Total minimal cost: 48 + 75 + 50 + 2,000 = 2,173 scalar multiplications.
Thus the optimal parenthesization is F1*(F2*(F3F4))*F5 (i.e., compute F3F4 first, then fold in F2, then F1, then F5). The only adjacent original pair explicitly multiplied in this optimal plan is F3F4.
A video solution is available for this question — log in and enroll to watch it.
Explore the full course: Iocl Engineers Officers Grade A Paper 2