GATE CS 2018 Q31 — Algorithm Design: Dynamic Programming

To find the optimal parenthesization of the matrix chain $F_1 F_2 F_3 F_4 F_5$, we use dynamic programming. The dimensions of the matrices are:

• $F_1: 2 \times 25$
• $F_2: 25 \times 3$
• $F_3: 3 \times 16$
• $F_4: 16 \times 1$
• $F_5: 1 \times 1000$

Let $m[i, j]$ denote the minimum number of scalar multiplications needed to compute the product $F_i \dots F_j$. We compute the values for chains of increasing length:

• Length 2:
  $m[1, 2] = 2 \times 25 \times 3 = 150$
  $m[2, 3] = 25 \times 3 \times 16 = 1200$
  $m[3, 4] = 3 \times 16 \times 1 = 48$
  $m[4, 5] = 16 \times 1 \times 1000 = 16000$
• Length 3:
  $m[1, 3] = \min(m[1, 2] + 2 \times 3 \times 16, m[2, 3] + 2 \times 25 \times 16) = \min(150 + 96, 1200 + 800) = 246$   $\rightarrow (F_1 F_2) F_3$
  $m[2, 4] = \min(m[2, 3] + 25 \times 16 \times 1, m[3, 4] + 25 \times 3 \times 1) = \min(1200 + 400, 48 + 75) = 123$   $\rightarrow F_2 (F_3 F_4)$
  $m[3, 5] = \min(m[3, 4] + 3 \times 1 \times 1000, m[4, 5] + 3 \times 16 \times 1000) = \min(48 + 3000, 16000 + 48000) = 3048$   $\rightarrow (F_3 F_4) F_5$
• Length 4:
  $m[1, 4] = \min(m[2, 4] + 2 \times 25 \times 1, m[1, 2] + m[3, 4] + 2 \times 3 \times 1, m[1, 3] + 2 \times 16 \times 1) = \min(123 + 50, 150 + 48 + 6, 246 + 32) = 173$   $\rightarrow F_1 (F_2 (F_3 F_4))$
  $m[2, 5] = \min(m[2, 4] + 25 \times 1 \times 1000, \dots) = 123 + 25000 = 25123$   $\rightarrow (F_2 (F_3 F_4)) F_5$
• Length 5:
  $m[1, 5] = \min(m[1, 4] + 2 \times 1 \times 1000, \dots) = 173 + 2000 = 2173$   $\rightarrow ((F_1 (F_2 (F_3 F_4))) F_5)$

The optimal parenthesization is $(((F_1 (F_2 (F_3 F_4))) F_5)$. In this structure, the only pair of adjacent matrices from the original chain that is directly multiplied is $F_3 F_4$. Thus, the only explicitly computed pair is $F_3 F_4$.