Matrix Chain Multiplication in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

7 practice sets · Page 1 of 1

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

Which of the following lines should be inserted to complete the above code?

arr[row][k] - arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];

arr[row][k] + arr[k + 1][col] - mat[row - 1] * mat[k] * mat[col];

arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];

arr[row][k] - arr[k + 1][col] - mat[row - 1] * mat[k] * mat[col];

View Answer

Correct Answer: C — arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];

Explanation:

The line arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col] should be inserted to complete the above code.

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?

O(n!)

O(n^{3})

O(n^{2})

Exponential

View Answer

Correct Answer: D — Exponential

Explanation:

The time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)^{th} Catalan number which is exponential.

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

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?

6050

7500

7750

12000

View Answer

Correct Answer: C — 7750

Explanation:

The minimum number of multiplications required is 7750.

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

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?

18000

12000

24000

32000

View Answer

Correct Answer: A — 18000

Explanation:

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

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

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?

10*20

20*30

10*30

102030

View Answer

Correct Answer: D — 102030

Explanation:

The number of multiplications required is 102030.

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

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?

dp[i,j] = 1 if (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]})

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

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

View Answer

Correct Answer: 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]).

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

Data Structure And AlgorithmMediumDynamic ProgrammingMatrix Chain Multiplication

Which of the following methods can be used to solve the matrix chain multiplication problem?

Dynamic programming

Brute force

Recursion

Dynamic Programming, Brute force, Recursion

View Answer

Correct Answer: D — Dynamic Programming, Brute force, Recursion

Explanation:

Dynamic Programming, Brute force, Recursion methods can be used to solve the matrix chain multiplication problem.