Virtual Gate Test Series: Algorithms - Matrix Chain Ordering

Question

Consider the following chain of matrices $A_{1}$ to $A_{4}$ having dimensions given below

$A_{1}\rightarrow 2\times 3$

$A_{2}\rightarrow 3\times 5$

$A_{3}\rightarrow 5\times 4$

$A_{4}\rightarrow 4\times 2$

The following table is filled up using dynamic programming in order to find minimum number of scalar multiplications$:$

What are the values of $P$ and $Q?$

1. $60,140$
2. $60,82$
3. $60,40$
4. $60,92$

Comments

I think B is Correct option

P  = 60
 

 

Q = 80

Answer 1

p=60,q=82

p=(3*5*4)=60

q=70+2*3*2=82

Comments

could u please elaborate the method.

---

how u are getting 82?

I think it should be 86.

ryt??

Answer 2

rrans is 60,  82

Comments

Isn't (A1xA2)x(A3xA4) is more optimal where (A1xA2) = 2x3x5 = 30 and (A3xA4) = 5x4x2 = 40 so (A1xA2)x(A3xA4) = 70

---

Finally, you have to multiply them. 70+(2*5*2)=90.

answer = min(82,86,90)=82