51. What is the value stored in ans[3][3] when the following code is executed?
#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[0][i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i][0] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}
#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[0][i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i][0] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}52. For which of the following inputs would Kadane's algorithm produce the INCORRECT output?
53. Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?
#include<stdio.h>
int max_num(int a,int b)
{
if(a> b)
return a;
return b;
}
int maximum_subarray_sum(int *arr, int len)
{
int sum[len], idx;
sum[0] = arr[0];
for(idx = 1; idx < len; idx++)
sum[idx] = _______________________;
int mx = sum[0];
for(idx = 0; idx < len; idx++)
if(sum[idx] > mx)
mx =sum[idx];
return mx;
}
int main()
{
int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
int ans = maximum_subarray_sum(arr, len);
printf("%d",ans);
return 0;
}
#include<stdio.h>
int max_num(int a,int b)
{
if(a> b)
return a;
return b;
}
int maximum_subarray_sum(int *arr, int len)
{
int sum[len], idx;
sum[0] = arr[0];
for(idx = 1; idx < len; idx++)
sum[idx] = _______________________;
int mx = sum[0];
for(idx = 0; idx < len; idx++)
if(sum[idx] > mx)
mx =sum[idx];
return mx;
}
int main()
{
int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
int ans = maximum_subarray_sum(arr, len);
printf("%d",ans);
return 0;
}54. Which of the following is/are property/properties of a dynamic programming problem?
55. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
56. Suppose you are given infinite coins of N denominations v1, v2, v3, ....., vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?
57. What is the time complexity of the following dynamic programming implementation used to compute the nth fibonacci term?
1. int fibo(int n)
2. int fibo_terms[100000] //arr to store the fibonacci numbers
3. fibo_terms[0] = 0
4. fibo_terms[1] = 1
5.
6. for i: 2 to n
7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.
9. return fibo_terms[n]
1. int fibo(int n)
2. int fibo_terms[100000] //arr to store the fibonacci numbers
3. fibo_terms[0] = 0
4. fibo_terms[1] = 1
5.
6. for i: 2 to n
7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.
9. return fibo_terms[n]58. Consider the following assembly line problem:
time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4
What is the minimum time required to build the car chassis?
time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 459. You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?
60. 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;
}
#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;
}Read More Section(Dynamic Programming in Data Structures)
Each Section contains maximum 100 MCQs question on Dynamic Programming in Data Structures. To get more questions visit other sections.