GATE CS 2018 Q.41 (CS Q.31): Dynamic Programming

Assume that multiplying a matrix $G_1$ of dimension $p \times q$ with another matrix $G_2$ of dimension $q \times r$ requires $pqr$ scalar multiplications. Computing the product of $n$ matrices $G_1 G_2 G_3 \dots G_n$ can be done by parenthesizing in different ways. Define $G_i G_{i+1}$ as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain $G_1 G_2 G_3 G_4 G_5 G_6$ using parenthesization $(G_1(G_2 G_3))(G_4(G_5 G_6))$ , $G_2 G_3$ and $G_5 G_6$ are the only explicitly computed pairs.

Consider a matrix multiplication chain $F_1 F_2 F_3 F_4 F_5$ , where matrices $F_1, F_2, F_3, F_4$ and $F_5$ are of dimensions $2 \times 25$ , $25 \times 3$ , $3 \times 16$ , $16 \times 1$ and $1 \times 1000$ , respectively. In the parenthesization of $F_1 F_2 F_3 F_4 F_5$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

$F_1 F_2$ and $F_3 F_4$ only

$F_2 F_3$ only

$F_3 F_4$ only

$F_1 F_2$ and $F_4 F_5$ only

Official answer and solution

Official answer: C
From: Official GATE 2018 answer key

Solution

Use dynamic programming for matrix chain multiplication to find the parenthesization that minimizes scalar multiplications.

Given matrix dimensions $d = [2, 25, 3, 16, 1, 1000]$ for matrices $F_1, F_2, F_3, F_4, F_5$ :

$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$

Compute costs for subchains:

Chain length 2:
- $F_1 F_2$ : $2 \times 25 \times 3 = 150$
- $F_2 F_3$ : $25 \times 3 \times 16 = 1200$
- $F_3 F_4$ : $3 \times 16 \times 1 = 48$
- $F_4 F_5$ : $16 \times 1 \times 1000 = 16000$
Chain length 3:
- $F_1..F_3$ : $\min((F_1 F_2)F_3: 150 + 2 \times 3 \times 16 = 246,\; F_1(F_2 F_3): 1200 + 2 \times 25 \times 16 = 2000) = 246$
- $F_2..F_4$ : $\min((F_2 F_3)F_4: 1200 + 25 \times 16 \times 1 = 1600,\; F_2(F_3 F_4): 48 + 25 \times 3 \times 1 = 123) = 123$ (split at $F_2(F_3 F_4)$ )
- $F_3..F_5$ : $\min((F_3 F_4)F_5: 48 + 3 \times 1 \times 1000 = 3048,\; F_3(F_4 F_5): 16000 + 3 \times 16 \times 1000 = 64000) = 3048$
Chain length 4:
- $F_1..F_4$ : $\min(F_1(F_2..F_4): 0 + 123 + 2 \times 25 \times 1 = 173,\; (F_1..F_3)F_4: 246 + 2 \times 16 \times 1 = 278) = 173$ with structure $F_1(F_2(F_3 F_4))$
Chain length 5 ( $F_1..F_5$ $F_{1} .. F_{5}$ ):
- Split $(F_1..F_4)F_5$ : $173 + 0 + 2 \times 1 \times 1000 = 2173$ .
- Any split involving $F_5$ earlier incurs much higher costs (e.g., $F_4 F_5$ alone is 16000).

The optimal parenthesization is $((F_1 (F_2 (F_3 F_4))) F_5)$ with total cost 2173.
In this parenthesization, the only base matrices multiplied directly together without an intermediate product are $F_3$ and $F_4$ ( $F_3 F_4$ ).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 41 of 65, printed as CS Q.31
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source