Matrix Multiplications

Parshu gate asked Dec 10, 2017 • edited Jan 31, 2020 by Lakshman Bhaiya

3,187 views

2 votes

Let $A1, A2, A3, A4, A5$ be five matrices of dimensions $2\times3, 3\times5, 5\times2, 2\times4, 4\times3$ respectively. The minimum number of scalar multiplications required to find the product $A1, A2 ,A3, A4, A5$ using the basic matrix multiplication method is_______

Algorithms
matrix-chain-ordering
dynamic-programming
algorithms

+ –

Parshu gate asked Dec 10, 2017 • edited Jan 31, 2020 by Lakshman Bhaiya

Parshu gate

3.2k views

See all

3 3 Comments

student2018

commented Dec 12, 2017

82 By multiplying (A1*(A2*A3)*A4*A5)

1 votes

Pramod Kumar 5

commented Jan 27, 2018

How 82 can you explain in brief sir

0 votes

Diksha Aswal

commented Jan 31, 2018

getting 78 ( ( A1 (A2*A3) ) (A4*A5) )

0 votes

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

3 votes

78 is the correct answer. The paranthesization is : (A₁(A₂A₃))(A₄A₅)

Somoshree Datta 5 answered Oct 9, 2018

Somoshree Datta 5

See all

5 5 Comments

Show 2 previous comments

divyan

commented Dec 19, 2018

@Karthik Selvam I think here total parenthesize ways will be 42

0 votes

Sanjay Sharma

commented Oct 20, 2021

no need for brute force , it is not practical to try 14 combinations. Take pairs which reduce resultant matrix size and also invovles inm lesser multiplications

0 votes

M_eight

commented Oct 20, 2021

Lakshman Patel RJIT

By applying the matrix multiplication method we can find the minimum no. of multiplication required and from that we can find the optimal parenthesis.

0 votes

Please log in or register to add a comment.

0 votes

88 by (((A1(A2A3))A4)A5)

Parveen Chahal 1 answered Dec 31, 2017

Parveen Chahal 1

See all

0 Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

1 votes

3 answers

Parshu gate asked Nov 27, 2017

4,281 views

Matrix chain multiplication
Which of the following is the recurrence relation for the matrix chain multiplication problem where p[i-1]*p[i] gives the dimension of the i^th matrix? dp[i,j]=1 if i=j dp[i,j]=min{dp[i,k]+dp[k+1,j]} dp[i,j]=1 if i=j dp[i,j]=min{dp[i,k]+dp[k+1,j]}+p[i-1]*p[k]*p[j] dp[i,j]= ... dp[i,j]=min{dp[i,k]+dp[k+1,j]} dp[i,j]=0 if i=j dp[i,j]=min{dp[i,k]+dp[k+1,j]}+p[i-1]*p[k]*p[j]

Which of the following is the recurrence relation for the matrix chain multiplication problem where p[i-1]*p[i] gives the dimension of the i^th matrix? dp[i,j]=1 if i=jd...

Parshu gate

4.3k views

Parshu gate asked Nov 27, 2017

Algorithms
dynamic-programming
algorithms
matrix-chain-ordering

+ –

1 votes

2 answers

firki lama asked Dec 29, 2016

1,188 views

Virtual Gate Test Series: Algorithms - Matrix Chain Ordering
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 ... of scalar multiplications$:$ What are the values of $P$ and $Q?$ $60,140$ $60,82$ $60,40$ $60,92$

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...

firki lama

1.2k views

firki lama asked Dec 29, 2016

Algorithms
algorithms
dynamic-programming
matrix-chain-ordering
virtual-gate-test-series

+ –

0 votes

1 answer

Rohan Mundhey asked Nov 11, 2016

1,577 views

Matrix Multiplication
Matrix multiplication is associative and matrix chain multiplication uses following matrices A1 is 30×35 A2 is 35×15 A3 is 15×5 A4 is 5×10 A5 is 10×20 A6 is 20×25 Find the minimum number of multiplications required to compute A1 A2 A3 A4A5A6

Matrix multiplication is associative and matrix chain multiplication uses following matricesA1 is 30×35A2 is 35×15A3 is 15×5A4 is 5×10A5 is 10×20A6 is 20×25Find the...

Rohan Mundhey

1.6k views

Rohan Mundhey asked Nov 11, 2016

Algorithms
algorithms
matrix-chain-ordering
dynamic-programming

+ –

2 votes

4 answers

sh!va asked Jul 12, 2016

22,150 views

Find he minimum number of scalar multiplications in matrix multiplication
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 ... 100, r = 20, s = 5, and t = 80, then what is the minimum number of scalar multiplications needed ?

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 multi...

sh!va

22.2k views

sh!va asked Jul 12, 2016

Algorithms
algorithms
matrix-chain-ordering

+ –

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

3 3 Comments reply

Please log in or register to add a comment.

Please log in or register to answer this question.

2 Answers

5 5 Comments reply

Please log in or register to add a comment.

0 reply

Please log in or register to add a comment.

Related questions

3 3 Comments

5 5 Comments

0