GATE CS 2011 Q.38 (CS Q.38): Dynamic Programming

Four matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $p \times q$ , $q \times r$ , $r \times s$ and $s \times t$ respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as $((M_1 \times M_2) \times (M_3 \times M_4))$ , the total number of scalar multiplications is $p q r + r s t + p r t$ . When multiplied as $(((M_1 \times M_2) \times M_3) \times M_4)$ , the total number of scalar multiplications is $p q r + p r s + p s t$ .

If $p = 10, q = 100, r = 20, s = 5$ , and $t = 80$ , then the minimum number of scalar multiplications needed is

248000

44000

19000

25000

Official answer and solution

Official answer: C
From: Official GATE 2011 answer key

Solution

Apply the dynamic programming Matrix Chain Multiplication algorithm to find the optimal parenthesization cost.

Matrix dimensions are given by array $d = [10, 100, 20, 5, 80]$ , where matrix $M_i$ has dimension $d_{i-1} \times d_i$ for $i \in \{1, 2, 3, 4\}$ .

Chain length 2 costs:

$m[1, 2] = d_0 d_1 d_2 = 10 \times 100 \times 20 = 20,000$
$m[2, 3] = d_1 d_2 d_3 = 100 \times 20 \times 5 = 10,000$
$m[3, 4] = d_2 d_3 d_4 = 20 \times 5 \times 80 = 8,000$

Chain length 3 costs:

For $m[1, 3]$ $m [1, 3]$ :
- Split at 1: $m[2, 3] + d_0 d_1 d_3 = 10,000 + 10 \times 100 \times 5 = 15,000$
- Split at 2: $m[1, 2] + d_0 d_2 d_3 = 20,000 + 10 \times 20 \times 5 = 21,000$
- Minimum $m[1, 3] = 15,000$ .
For $m[2, 4]$ $m [2, 4]$ :
- Split at 2: $m[3, 4] + d_1 d_2 d_4 = 8,000 + 100 \times 20 \times 80 = 168,000$
- Split at 3: $m[2, 3] + d_1 d_3 d_4 = 10,000 + 100 \times 5 \times 80 = 50,000$
- Minimum $m[2, 4] = 50,000$ .

Chain length 4 ( $m[1, 4]$ ):

Split at 1: $m[2, 4] + d_0 d_1 d_4 = 50,000 + 10 \times 100 \times 80 = 130,000$
Split at 2: $m[1, 2] + m[3, 4] + d_0 d_2 d_4 = 20,000 + 8,000 + 10 \times 20 \times 80 = 44,000$
Split at 3: $m[1, 3] + d_0 d_3 d_4 = 15,000 + 10 \times 5 \times 80 = 15,000 + 4,000 = 19,000$

The global minimum scalar multiplications needed is 19,000.

Final answer

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

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 38 of 65, printed as CS Q.38
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