GATE CS 2016 Set 2 Q38 — Algorithm Design: Dynamic Programming

We are given four matrices with dimensions:

• $A_1: 10 \times 5$
• $A_2: 5 \times 20$
• $A_3: 20 \times 10$
• $A_4: 10 \times 5$

The dimension array is $p = [10, 5, 20, 10, 5]$. We can find the minimum number of scalar multiplications using the dynamic programming approach for the Matrix Chain Multiplication problem.

Let $m[i, j]$ denote the minimum multiplications to compute $A_i \dots A_j$:

• Chain length 2:
  • $m[1, 2] = 10 \times 5 \times 20 = 1000$
  • $m[2, 3] = 5 \times 20 \times 10 = 1000$
  • $m[3, 4] = 20 \times 10 \times 5 = 1000$
• Chain length 3:
  • $m[1, 3] = \min(m[1, 1] + m[2, 3] + 10 \times 5 \times 10,\; m[1, 2] + m[3, 3] + 10 \times 20 \times 10) = \min(1500, 3000) = 1500$
  • $m[2, 4] = \min(m[2, 2] + m[3, 4] + 5 \times 20 \times 5,\; m[2, 3] + m[4, 4] + 5 \times 10 \times 5) = \min(1500, 1250) = 1250$
• Chain length 4:
  • $m[1, 4] = \min \begin{cases} m[1, 1] + m[2, 4] + 10 \times 5 \times 5 = 0 + 1250 + 250 = 1500 \\ m[1, 2] + m[3, 4] + 10 \times 20 \times 5 = 1000 + 1000 + 1000 = 3000 \\ m[1, 3] + m[4, 4] + 10 \times 10 \times 5 = 1500 + 0 + 500 = 2000 \end{cases}$

Thus, the minimum number of scalar multiplications is $\mathbf{1500}$, achieved by the parenthesization $A_1((A_2 A_3)A_4)$.