# Data Structure Questions and Answers-Matrix-chain Multiplication

## Click on any option to know the CORRECT ANSWERS

 Question 1
Which of the following methods can be used to solve the matrix chain multiplication problem?
 A Dynamic programming B Brute force C Recursion D All of the mentioned

Question 1 Explanation:
All of the mentioned methods can be used to solve the matrix chain multiplication problem.

 Question 2
Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?
 A dp[i, j] = 1 if i=j dp[i, j] = min{dp[i, k] + dp[k+1, j]} B dp[i, j] = 0 if i=j dp[i, j] = min{dp[i, k] + dp[k+1, j]} C dp[i, j] = 1 if i=j dp[i, j] = min{dp[i, k] + dp[k+1, j]} + mat[i-1]*mat[k]*mat[j]. D dp[i, j] = 0 if i=j dp[i, j] = min{dp[i, k] + dp[k+1, j]} + mat[i-1]*mat[k]*mat[j].

Question 2 Explanation:
The recurrence relation is given by:

dp[i, j] = 0 if i=j

dp[i, j] = min{dp[i, k] + dp[k+1, j]} + mat[i-1]*mat[k]*mat[j].

 Question 3
Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?
 A 10*20 B 20*30 C 10*30 D 10*20*30

Question 3 Explanation:
The number of multiplications required is 10*20*30.

 Question 4
Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?
 A 18000 B 12000 C 24000 D 32000

Question 4 Explanation:
The minimum number of multiplications are 18000. This is the case when the matrices are parenthesized as (P*Q)*R.

 Question 5
Consider the matrices P, Q, R and S which are 20 x 15, 15 x 30, 30 x 5 and 5 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the four matrices?
 A 6050 B 7500 C 7750 D 12000