Register

Matrix chain multiplication

5,334 views
1 1 vote

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?

  1.   dp[i,j]=1 if i=j
    dp[i,j]=min{dp[i,k]+dp[k+1,j]}
  2.   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]
  3.   dp[i,j]=0 if i=j
    dp[i,j]=min{dp[i,k]+dp[k+1,j]}
  4.   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]

3 Answers

Voting & Accepting an answer helps improve the community
← Previous · set associative mapp...Next → · probability
← Previous in category · What kind of For loo...Next in category → · Doubt in this questi...
Position:
Show:

Related questions

1 1 vote
2 2 answers
2.3k
2.3k views
firki lama asked Dec 29, 2016
2,270 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...
0 0 votes
1 1 answer
2.7k
2.7k views
Rohan Mundhey asked Nov 11, 2016
2,716 views
Matrix Multiplication
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 minim...
0 0 votes
1 1 answer
1.2k
1.2k views
shruti gupta1 asked Jun 29, 2018
1,213 views
matrics multiplication
31. Consider the problem of a chain $$ of four matrices. Suppose that the dimensions of the matrices $A_{1}, A_{2}, A_{3}$ and $A_{4}$ are $30 \times 35$, $35 \times 15,1...
1 1 vote
1 1 answer
86
86 views
GO Classes asked Aug 21
86 views
GO Classes DPP | GATE CS, DA | Algorithms | Matrix Chain Multiplication
Consider four matrices whose dimension array is:$p=[5,2,2,4,6]$Thus:$A_1:5\times2$$A_2:2\times2$$A_3:2\times4$$A_4:4\times6$Using optimal matrix-chain multiplication, wha...