Matrix Chain Multiplication in Data Structure And Algorithm: Practice MCQ Questions and Answers

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];

Answer and explanation

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

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

Answer and explanation

Correct Answer: D — Exponential

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

Answer and explanation

Correct Answer: C — 7750

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

Answer and explanation

Correct Answer: A — 18000

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

Answer and explanation

Correct Answer: D — 10*20*30

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

Answer and explanation

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

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

Answer and explanation

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

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

Printing this content is disabled

Matrix Chain Multiplication in Data Structure And Algorithm: Practice MCQ Questions and Answers