Test by Bikram | Algorithms | Test 2 | Question: 23

Question

Matrix multiplication is associative and MCS ( matrix chain multiplication ) uses the following matrices:

$\begin{array} \text{M1} & 10^* 100 \\ M2 & 100^* 5 \\ M3 &  5^* 50 \\ M4 & 50^* 1 \end{array}$

The number of orderings that are possible to compute $M1 \ M2 \ M3 \ M4$ are _________.

Comments

Ans should be 0 for this.

I think question framing is wrong here

---

@ Deependra

Now it is correct, please check ,

#row of  M2 = #column of M1,

and  #row of  M4 = #column of M3, so both are compatible with each other..

---

@ bikram sir it's correct now...

Answer 1

Given  M1  M2  M3  M4

1. M1  ( M2 ( M3  M4) )
2. M1 ( ( M2 M3)  M4 ) 
3. (M1 M2)  (M3 M4)
4. ( (M1 M2) M3 ) M4
5. ( M1 (M2 M3) ) M4

Hence total number of orderings are 5 .

Comments

Though question doesn`t ask this bu out of these 5 ordering , first one is minimal with 1750 operations?

---

 saxena0612

yes, first order is minimum.

1st order = 1750 operations ( min )

2nd order =  31,000

3rd order = 5300

4th order =  8000 

5th order = 75, 500 ( max)

Answer 2

For n+1 matrices  no of parenthesis Pattern possible is Cn where C-Catlan no

Cn=(2n)Cn / n+1

Here n+1=4