Data Structure Multiple Choice Questions 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
Answer: d
Clarification: 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].
Answer: d
Clarification: 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
Answer: d
Clarification: 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
Answer: a
Clarification: 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
Answer: c
Clarification: The minimum number of multiplications required is 7750.
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
Answer: d
Clarification: 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
#include
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];
Answer: c
Clarification: 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
#include
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)
View Answer
Answer: d
Clarification: 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
#include
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)
Answer: c
Clarification: 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
#include
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
Answer: a
Clarification: 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
#include
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
Answer: b
Clarification: 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
#include
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
View Answer
Answer: c
Clarification: 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
#include
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
View Answer
Answer: c
Clarification: The output of the program is 64000.
and Answers.