retagged by
18,867 views
30 votes
30 votes

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 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. $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
retagged by

6 Answers

1 votes
1 votes
(F1 ( F2 ( F3 F4) ) ) ( F5 ) = 48+75+50+2000 = 2173 multiplications so option (c) is the answer
–1 votes
–1 votes

I also marked A.but ans is C.run on geeks for geek.

Answer:

Related questions

38 votes
38 votes
5 answers
1
gatecse asked Feb 14, 2018
21,937 views
Consider the weights and values of items listed below. Note that there is only one unit of each item.$$\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weigh...
35 votes
35 votes
9 answers
2
gatecse asked Feb 14, 2018
17,335 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...
35 votes
35 votes
7 answers
3