# Data Structure Questions and Answers – Matrix-chain Multiplication

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Matrix-chain Multiplication”.

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) Dynamic Programming, Brute force, Recursion

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

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

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

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

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

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

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

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

Explanation: The minimum number of multiplications required is 7750.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. 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?
a) O(n!)
b) O(n3)
c) O(n2)
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.

7. Consider the following dynamic programming implementation of the matrix chain problem:

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = ________________________;
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n - 1];
}
int main()
{
int mat[6] = {20,5,30,10,40};
int ans = mat_chain_multiplication(mat,5);
printf("%d",ans);
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) arr[row][k] – arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col];
b) arr[row][k] + arr[k + 1][col] – mat[row – 1] * mat[k] * mat[col];
c) arr[row][k] + arr[k + 1][col] + mat[row – 1] * mat[k] * mat[col];
d) 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.

8. What is the time complexity of the following dynamic programming implementation of the matrix chain problem?

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n - 1];
}
int main()
{
int mat[6] = {20,5,30,10,40};
int ans = mat_chain_multiplication(mat,5);
printf("%d",ans);
return 0;
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The time complexity of the above dynamic programming implementation of the matrix chain multiplication is O(n3).

9. What is the space complexity of the following dynamic programming implementation of the matrix chain problem?

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n - 1];
}
int main()
{
int mat[6] = {20,5,30,10,40};
int ans = mat_chain_multiplication(mat,5);
printf("%d",ans);
return 0;
}```

a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Explanation: The space complexity of the above dynamic programming implementation of the matrix chain multiplication is O(n2).

10. What is the output of the following code?

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n - 1];
}
int main()
{
int mat[6] = {20,30,40,50};
int ans = mat_chain_multiplication(mat,4);
printf("%d",ans);
return 0;
}```

a) 64000
b) 70000
c) 120000
d) 150000

Explanation: The program prints the minimum number of multiplications required, which is 64000.

11. What is the value stored in arr[2][3] when the following code is executed?

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n - 1];
}
int main()
{
int mat[6] = {20,30,40,50};
int ans = mat_chain_multiplication(mat,4);
printf("%d",ans);
return 0;
}```

a) 64000
b) 60000
c) 24000
d) 12000

Explanation: The value stored in arr[2][3] when the above code is executed is 60000.

12. What is the output of the following code?

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n-1];
}
int main()
{
int mat[6] = {10,10,10,10,10,10};
int ans = mat_chain_multiplication(mat,6);
printf("%d",ans);
return 0;
}```

a) 2000
b) 3000
c) 4000
d) 5000

Explanation: The program prints the minimum number of multiplications required to multiply the given matrices, which is 4000.

13. What is the output of the following code?

```#include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n];
int i,k,row,col,len;
for(i=1;i<n;i++)
arr[i][i] = 0;
for(len = 2; len < n; len++)
{
for(row = 1; row <= n - len + 1; row++)
{
col = row + len - 1;
arr[row][col] = INT_MAX;
for(k = row; k <= col - 1; k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col];
if(tmp < arr[row][col])
arr[row][col] = tmp;
}
}
}
return arr[1][n-1];
}
int main()
{
int mat[6] = {20,25,30,35,40};
int ans = mat_chain_multiplication(mat,5);
printf("%d",ans);
return 0;
}```

a) 32000
b) 28000
c) 64000
d) 70000

Explanation: The output of the program is 64000.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]