The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
2.7k views

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 $pqr + rst + prt$. When multiplied as $(((M_1 \times M_2) \times M_3) \times M_4)$, the total number of scalar multiplications is $pqr + prs + pst$.

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

  1.  $248000$
  2.  $44000$
  3.  $19000$
  4.  $25000$
asked in Algorithms by Veteran (101k points)
edited by | 2.7k views
+3

19,000 is the correct answer!
 

+2

This Might Help ...

2 Answers

+27 votes
Best answer

Answer is C.

$\text{ Ordering: }\\ \text{ First Multiply } M_2 \times M_3. \text{ This requires 100*20*5 multiplications.}$ $\text{ Then Multiply } M_1 \times (M_2 \times M_3). \text{ This requires 10*100*5 multiplications. }$ $\text{ Then Multiply } (M_1 \times (M_2 \times M_3)) \times M_4. \text{ This requires 10*5*8 multiplications. }$ $\text{ Total 19000 Multiplications.}$


Brute Force approach - anyone can do. 

No. of possible ordering for 4 matrices is $C_3$ where $C_3$ is the $3^{rd}$ Catalan number and given by $n=3$ in $\frac{1}{n+1} {}^{2n}C_n = 5.$

So, here we have 

  1. $(M_1 \times M_2) \times (M_3 \times M_4)$
  2. $(M_1 \times (M_2 \times M_3)) \times M_4$
  3. $((M_1 \times M_2) \times M_3) \times M_4$
  4. $M_1 \times (M_2 \times (M_3 \times M_4))$
  5. $M_1 \times ((M_2 \times M_3) \times M_4))$

Each of these would give no. of multiplications required as

  1. $pqr + rst + prt $
  2. $qrs + pqs + pst$
  3. $pqr + prs + pst$
  4. $rst + qrt + pqt$
  5. $qrs + qst + pst$

The last 2 are having $qt$ terms which are the highest terms by far and hence we can avoid them from consideration $qt = 8000$ multiplied by one other term would be larger than any value in choice. So, just find the value of first 3 terms. 

  1. $pqr + rst + prt  = 20000 + 8000 + 16000 = 44000$
  2. $qrs + pqs + pst = 10000 + 5000 + 4000 = 19000$ - smallest value in choice, we can stop here. 
  3. $pqr + prs + pst$

Dynamic Programming Solution (should know Matrix Chain Ordering algorithm)

Here we have a chain of length 4.

Dynamic programming solution of Matrix chain ordering has the solution

$m[i, j] = \begin{cases} 0 &\text{ if } i=j\\ \min_{i\leq k < j } m[i]k] + m[k+1][j] + p_{i-1}p_{j}p_{k} &\text{ if } i < j\end{cases}$

So, we can fill the following table starting with the diagonals and moving upward diagonally. Here $k < j$ but $\geq i.$

  j=1 j=2 j=3 j=4
i=1 0

$p_0p_1p_2 =
\\ 20000$

$\min(10000+p_0p_1p_3,
\\20000+p_0+p_2p_3)
\\=15000$

$\min(18000+ p_0p_1p_4, \\20000+8000+p_0+p_2+p_4, \\15000+p_0p_3p_4) = \\19000$
i=2   0 $p_1p_2p_3 = 10000$ $\min(10000 + p_2p_3p_4), \\p_1p_3p_4) = 18000$
i=3     0 $p_2p_3p_4 = 8000$
i=4       0

Our required answer is given by $m[1,4] = 19000.$

answered by Active (4.2k points)
edited by
0
checked all combinations in the exam? any shortcuts?
+2
Use dynamic programming approach. It is standard matrix multiplication problem.
0
even the dynamic one takes time. how to approach this kind of problem in lesser time??
+4
It is just 5 pairs we have to consider. Dynamic programming is recommended if one has tried it before- then its easy to try for problems. See the solution now.
+3

Values are obtained by the formula: m[i,j] = { 0                                                                                     ,         i==j

                                                                                       min i<=k<j    { m[i,k] + m[k+1,j] + Pi-1.Pk.Pj }       ,        i < j

                                                                                       }

DP table
0 20000 15000 19000
  0 10000 50000
    0 8000
      0

ans: 19000(option C)

0
How to solve such matrix chain multiplication questions fast in Exam ??
+7 votes

For those who still doen't understand how multiplication works, very simple.

Only thing is you should not alter the sequence.

For ex, (M1 x M2) = First term X Common Term X Last term

(M1.x M2) = (10 x 100 ) x ( 100 x 20) = 10 x 100 x 20

((M1  x M2 ) x M3) = (10 x 100 x 20) x (20 x 5) = 10 x 20 x 5 ( In this case, we have cancelled all remaining terms except first term, common term and last term)

(((M1  x M2 ) x M3) x M4) = (10 x 20 x 5) x (5 x 80) = 10 x 5 x 80 ( In this case also, we have cancelled all remaining terms except first term, common term and last term)

Finally, addition of all steps will give us result.

Result = (10 x 100 x 20) + (10 x 20 x 5) + (10 x 5 x 80) = 19000

Isn't it simple !

answered by (175 points)
0
25000?
0
Plz aad total no
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,823 comments
57,593 users