GATE CS 2018 (Forenoon) — Question 41

AlgorithmsDynamic Programming InfrastructureMCQ2 marks · −2/3 if wrongHard

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_i G_{i+1}\) as an explicitly computed pair for a given paranthesization 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 \times 25, 25 \times 3, 3 \times 16, 16 \times 1\) and \(1 \times 1000\), 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. A
    \(F_1F_2\) and \(F_3F_4\) only
  2. B
    \(F_2F_3\) only
  3. C
    \(F_3F_4\) only
  4. D
    \(F_1F_2\) and \(F_4F_5\) only
Practise the full 2018-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Dynamic Programming InfrastructureTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group