21. You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?
22. What is the time complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence?
#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max;
int LIS[len]; // array to store the lengths of the longest increasing subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j];
}
}
LIS[i] = tmp_max + 1;
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
int ans = longest_inc_sub(arr, len);
printf("%d",ans);
return 0;
}
#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max;
int LIS[len]; // array to store the lengths of the longest increasing subsequence
LIS[0]=1;
for(i = 1; i < len; i++)
{
tmp_max = 0;
for(j = 0; j < i; j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j];
}
}
LIS[i] = tmp_max + 1;
}
int max = LIS[0];
for(i = 0; i < len; i++)
if(LIS[i] > max)
max = LIS[i];
return max;
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
int ans = longest_inc_sub(arr, len);
printf("%d",ans);
return 0;
}23. 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
For the optimal solution, which should be the starting assembly line?
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 = 424. For every non-empty string, the length of the longest palindromic subsequence is at least one.
25. 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?
26. There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?
27. What is the space complexity of Kadane's algorithm?
28. What is the output of the following code?
#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[] = {5, 6, 7, 10, 3, 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[] = {5, 6, 7, 10, 3, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}29. Consider the following recursive implementation of the rod cutting problem:
#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
max_price = max_of_two(_____________); // subtract 1 because index starts from 0
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}
Complete the above code.
#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
if(a > b)
return a;
return b;
}
int rod_cut(int *prices, int len)
{
int max_price = INT_MIN; // INT_MIN is the min value an integer can take
int i;
if(len <= 0 )
return 0;
for(i = 0; i < len; i++)
max_price = max_of_two(_____________); // subtract 1 because index starts from 0
return max_price;
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}30. What is the output of the following code?
#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;
}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.