GATE CS 2018 Set 1 — Question 41

This is a matrix chain multiplication problem. We need to find the optimal parenthesization for the product $F_1F_2F_3F_4F_5$.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 the dimension array be $p = [2, 25, 3, 16, 1, 1000]$. So $p_0=2, p_1=25, p_2=3, p_3=16, p_4=1, p_5=1000$.
We use dynamic programming. Let $m[i, j]$ be the minimum cost to compute the product $F_i...F_j$.Length 2:

• $m[1,2] = p_0 p_1 p_2 = 2 \times 25 \times 3 = 150$
• $m[2,3] = p_1 p_2 p_3 = 25 \times 3 \times 16 = 1200$
• $m[3,4] = p_2 p_3 p_4 = 3 \times 16 \times 1 = 48$
• $m[4,5] = p_3 p_4 p_5 = 16 \times 1 \times 1000 = 16000$

Length 3:

• $m[1,3] = \min(m[1,1]+m[2,3]+p_0p_1p_3, m[1,2]+m[3,3]+p_0p_2p_3) = \min(0+1200+2 \cdot 25 \cdot 16, 150+0+2 \cdot 3 \cdot 16) = \min(2000, 246) = 246$. Split at $k=2$, i.e., $(F_1F_2)F_3$.
• $m[2,4] = \min(m[2,2]+m[3,4]+p_1p_2p_4, m[2,3]+m[4,4]+p_1p_3p_4) = \min(0+48+25 \cdot 3 \cdot 1, 1200+0+25 \cdot 16 \cdot 1) = \min(123, 1600) = 123$. Split at $k=2$, i.e., $F_2(F_3F_4)$.
• $m[3,5] = \min(m[3,3]+m[4,5]+p_2p_3p_5, m[3,4]+m[5,5]+p_2p_4p_5) = \min(0+16000+3 \cdot 16 \cdot 1000, 48+0+3 \cdot 1 \cdot 1000) = \min(64000, 3048) = 3048$. Split at $k=4$, i.e., $(F_3F_4)F_5$.

Length 4:

• $m[1,4] = \min(m[1,1]+m[2,4]+p_0p_1p_4, m[1,2]+m[3,4]+p_0p_2p_4, m[1,3]+m[4,4]+p_0p_3p_4)$
• $k=1: 0 + 123 + 2 \cdot 25 \cdot 1 = 173$
• $k=2: 150 + 48 + 2 \cdot 3 \cdot 1 = 204$
• $k=3: 246 + 0 + 2 \cdot 16 \cdot 1 = 278$
• $m[1,4] = 173$. Split at $k=1$, i.e., $F_1(F_2F_3F_4)$, where $F_2F_3F_4$ is $F_2(F_3F_4)$. So, $F_1(F_2(F_3F_4))$.

Length 5:

• $m[1,5] = \min_{1 \le k < 5} (m[1,k] + m[k+1,5] + p_0 p_k p_5)$
• $k=1: m[1,1]+m[2,5]+p_0p_1p_5$. We need $m[2,5]$.
• $m[2,5] = \min(m[2,2]+m[3,5]+p_1p_2p_5, m[2,3]+m[4,5]+p_1p_3p_5, m[2,4]+m[5,5]+p_1p_4p_5)$
• $k=2: 0+3048+25 \cdot 3 \cdot 1000 = 78048$
• $k=3: 1200+16000+25 \cdot 16 \cdot 1000 = 417200$
• $k=4: 123+0+25 \cdot 1 \cdot 1000 = 25123$
• $m[2,5] = 25123$.
• Cost for $k=1$ in $m[1,5]$ is $0 + 25123 + 2 \cdot 25 \cdot 1000 = 75123$.
• $k=2: m[1,2]+m[3,5]+p_0p_2p_5 = 150 + 3048 + 2 \cdot 3 \cdot 1000 = 9198$.
• $k=3: m[1,3]+m[4,5]+p_0p_3p_5 = 246 + 16000 + 2 \cdot 16 \cdot 1000 = 48246$.
• $k=4: m[1,4]+m[5,5]+p_0p_4p_5 = 173 + 0 + 2 \cdot 1 \cdot 1000 = 2173$.

The minimum cost is $m[1,5] = 2173$, with the final split at $k=4$. This corresponds to the parenthesization $(F_1F_2F_3F_4)F_5$.
The parenthesization for $F_1F_2F_3F_4$ was found to be $F_1(F_2(F_3F_4))$.
So the full optimal parenthesization is $(F_1(F_2(F_3F_4)))F_5$.According to the problem definition, an "explicitly computed pair" is a pair of adjacent original matrices $G_iG_{i+1}$ that are directly multiplied.
In the optimal parenthesization $(F_1(F_2(F_3F_4)))F_5$, the first multiplication performed is $F_3F_4$. This is a pair of adjacent original matrices.
The subsequent multiplications are:

• $F_2 \times (F_3F_4)$
• $F_1 \times (F_2(F_3F_4))$
• $(F_1(F_2(F_3F_4))) \times F_5$

None of these subsequent multiplications involve two adjacent matrices from the original sequence $F_1, F_2, F_3, F_4, F_5$.
Therefore, the only explicitly computed pair is $F_3F_4$.