Redirected
recategorized by
2,151 views
1 votes
1 votes

Consider the problem of a chain $\langle A_{1}, A_{2}, A_{3}\rangle$ of three matrices. Suppose that the dimensions of the matrices are $10 \times 100$, $100 \times 5$ and $5 \times 50$ respectively. There are two different ways of parenthesization : (i) $((A_{1} A_{2} )A_{3} )$ and (ii) $(A_{1} (A_{2} A_{3}))$. Computing the product according to the first parenthesization is ______ times faster in comparison to the second parenthesization.

  1. $5$
  2. $10$
  3. $20$
  4. $100$ 
recategorized by

4 Answers

3 votes
3 votes

Using matrix multiplication method.

A is pxq and B is qxr then AB contains pqr no of multiplications.

if c is rxs then ((AB)C) no of multiplications=pqr+prs.

Using above statements find no of multiplications for two matrices.

Case I)

A1 =10x100,A2=100x5,A3=5x50.

((A1A2)A3) :first find A1A2(=P) no of muls=10*100*5=5000.//A1A2= P(assume)

then PA3 : P is 10x5 and A3 is 5x50

no of muls=10*5*50=2500.

Total no of multiplications=5000+2500=7500.

Case II)

(A1(A2A3)) :first A2A3(=Q) no of muls=100*5*50=25000.//A2A3=Q(assume)

(A1Q). Q is 100x50 and A1 is 10x100.

no of muls=10*100*50=50000.

Total no of multiplications=50000+25000=75000.

Compare both first one is 10 times faster than 2nd one.

2 votes
2 votes

Assume one multiplication take 1 msec.

i. will take 7500 multiplication = 7500 * 1 msec= 7500 msec

ii. will take 75000 multiplication = 75000 * 1 msec= 75000 msec

Faster=  75000 / 7500 = 10 

Ans is B.

1 votes
1 votes
Here (A1A2)A3=7500

And A1(A2A3)=75000

So first is 10 time faster then second one.
1 votes
1 votes

Case I)

A1 =10x100,A2=100x5,A3=5x50.

((A1A2)A3) :first find A1A2(=P) no of muls=10*100*5=5000.//A1A2= P(assume)

then PA3 : P is 10x5 and A3 is 5x50

no of muls=10*5*50=2500.

Total no of multiplications=5000+2500=7500.

Case II)

(A1(A2A3)) :first A2A3(=Q) no of muls=100*5*50=25000.//A2A3=Q(assume)

(A1Q). Q is 100x50 and A1 is 10x100.

no of muls=10*100*50=50000.

Total no of multiplications=50000+25000=75000.

Compare both first one is 10 times faster than 2nd one.

Answer:

Related questions

1 votes
1 votes
1 answer
2
makhdoom ghaya asked Jul 28, 2016
3,597 views
We can show that the clique problem is $NP$-hard by proving thatCLIQUE $\leq$ P 3-CNF_SATCLIQUE $\leq$ P VERTEX_COVERCLIQUE $\leq$ P SUBSET_SUMNone of the above
1 votes
1 votes
1 answer
3
makhdoom ghaya asked Jul 28, 2016
2,015 views
Match the following $:$$\begin{array}{} & \textbf{List – I} & & \textbf{List – II} \\ \text{a.} & \text{Bucket sort} & \text{i.} & O(n^3\lg n) \\ \text{b.} & \text...
3 votes
3 votes
2 answers
4
makhdoom ghaya asked Jul 28, 2016
1,871 views
Any decision tree that sorts $n$ elements has height$\Omega(n)$$\Omega(\text{lg}n)$$\Omega(n \text{lg} n)$$\Omega(n^2)$