+2 votes
5.8k views
Four matrices M1, M2, M3, and M4 have dimensions p x q, q x r, r x s, and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 x M2) x (M3 x M4)) total number of scalar multiplications is pqr + rst + prt.

When multiplied as (((Mi x M2) x M3) x M4) the total number of scalar multiplications is pqr + prs + pst.

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

recategorized | 5.8k views
0
Answer is 19000

How to solve this?
0
ans = 19000  ??
0
Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.

## 4 Answers

+8 votes 19000 is the ryt ans

by Active (4.8k points)
0
which algorithm you are using ...bro

i mean name of this algo?
+5 votes

Answer is 19000 multiplication

On multiplying M110*100 M2100*20 Number of scalar multiplications needed is 10*100*20 = 20000
M1  M2  M3  M4 can be multiplie in 5 different ways depicted in the following figure . We need to take the minimum of them all . by Boss (21.2k points)
0
Oops. Sorry I dont know how to simplify more than this . Everything is explained in the Answer. What difficulty do you find ?
0
@sittian if you try to be specific I might help .
0

@sittian

here for 4 matrices, in how many ways u can multiply them is shown......and for each multiplication cost associated with it is mentioned...u have to chose minimum for that...bottom up evaluation  of DP is used...

if u still have some doubt then u can refer to

https://gateoverflow.in/76732/now-waiting-for-best-answer

0
0
Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.
+1 vote
A=10*100

B=100*20

C=20*5

D=5*80

m going to use DP bottom up evaluation tabular approach to find min no of scalar multiplication...

we will start with

(1,1),(2,2),(3,3),(4,4)....they all will be 0
now, compute

(1,2)=10*100*20=20.000
(2,3)=100*20*5=10,000
(3,4)=20*5*80=8000

now,

(1,3)=min{      (1,1)+(2,3)+10*100*5                         =15,000
(1,2)+(3,3)+10*20*5
}

(2,4)=min{      (2,2)+(3,4)+100*20*80                       =50,000
(2,3)+(4,4)+100*5*80
}

finally compute

(1,4)=min {     (1,1)+(2,4)+10*100*80
(1,2)+(4,4)+10*20*80            =19,000(Ans!!)
(1,3)+(4,4)+10*5*80
​​​​​​​                                                     }
by Boss (19.5k points)
0
Is there any shortcut or Trick to get min number of multiplication faster? I mean if we could know the right split.
0 votes

19000 is the correct answer. by (11 points)

0 votes
2 answers
1
0 votes
1 answer
3
+1 vote
0 answers
4
+2 votes
1 answer
5
+1 vote
1 answer
7