The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
5.7k 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 ?
asked in Algorithms by Boss (35.5k points)
recategorized by | 5.7k 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

answered by Active (5k 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 .

answered by Boss (22.6k 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
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
​​​​​​​                                                     }
answered by Boss (19.7k 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.

answered by (11 points)

Related questions

0 votes
1 answer
3
asked Oct 26, 2016 in Algorithms by jenny101 Active (1.4k points) | 356 views
+1 vote
0 answers
4
asked Dec 15, 2016 in Algorithms by santhoshdevulapally Boss (12.9k points) | 133 views
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
49,434 questions
53,630 answers
186,007 comments
70,899 users