The GATE Grind

GATE 2018 CS – Question 41

Algorithms · Dynamic Programming · 2 marks · Multiple choice

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_1G_2G_3\dots G_n$ can be done by parenthesizing in different ways. Define $G_iG_{i+1}$ as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain $G_1G_2G_3G_4G_5G_6$ using parenthesization $(G_1(G_2G_3))(G_4(G_5G_6))$, $G_2G_3$ and $G_5G_6$ are the only explicitly computed pairs.

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

  1. $F_1F_2$ and $F_3F_4$ only
  2. $F_2F_3$ only
  3. $F_3F_4$ only
  4. $F_1F_2$ and $F_4F_5$ only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $F_3F_4$ only

Explanation

The cheapest parenthesization is $(F_1(F_2(F_3F_4)))F_5$: first $F_3F_4$ ($3\cdot16\cdot1=48$) gives a $3\times1$ matrix, then $F_2\cdot(3\times1)$ costs $25\cdot3\cdot1=75$, then $F_1\cdot(25\times1)$ costs $50$, and finally $\times F_5$ costs $2\cdot1\cdot1000=2000$, for a total of 2173. The only pair of original matrices multiplied directly is $F_3F_4$.