91. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
92. What is the output of the following program?
#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx];
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}
#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
int max_val[len + 1];
int i,j,tmp_price,tmp_idx;
max_val[0] = 0;
for(i = 1; i <= len; i++)
{
int tmp_max = INT_MIN; // minimum value an integer can hold
for(j = 1; j <= i; j++)
{
tmp_idx = i - j;
//subtract 1 because index of prices starts from 0
tmp_price = prices[j-1] + max_val[tmp_idx];
if(tmp_price > tmp_max)
tmp_max = tmp_price;
}
max_val[i] = tmp_max;
}
return max_val[len];
}
int main()
{
int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
int ans = rod_cut(prices, len_of_rod);
printf("%d",ans);
return 0;
}93. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:
fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4)
+ fibonacci(3) + fibonacci(3) + fibonacci(2)
:
:
:
Which property is shown by the above function calls?
fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4)
+ fibonacci(3) + fibonacci(3) + fibonacci(2)
:
:
:94. Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
95. What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?
96. What is the output of the following program?
#include<stdio.h>
int fibo(int n)
{
if(n<=1)
return n;
return fibo(n-1) + fibo(n-2);
}
int main()
{
int r = fibo(50000);
printf("%d",r);
return 0;
}
#include<stdio.h>
int fibo(int n)
{
if(n<=1)
return n;
return fibo(n-1) + fibo(n-2);
}
int main()
{
int r = fibo(50000);
printf("%d",r);
return 0;
}97. For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
98. You are given a rod of length 5 and the prices of each length are as follows:
length price
1 2
2 5
3 6
4 9
5 9
What is the maximum value that you can get after cutting the rod and selling the pieces?
length price
1 2
2 5
3 6
4 9
5 9
What is the maximum value that you can get after cutting the rod and selling the pieces?99. Fill in the blank to complete the code.
#include<stdio.h>
int main()
{
int coins[10]={1,3,4},lookup[100000];
int i,j,tmp,num_coins = 3,sum=100;
lookup[0]=0;
for(i = 1; i <= sum; i++)
{
int min_coins = i;
for(j = 0;j < num_coins; j++)
{
tmp = i - coins[j];
if(tmp < 0)
continue;
if(lookup[tmp] < min_coins)
______________;
}
lookup[i] = min_coins + 1;
}
printf("%d",lookup[sum]);
return 0;
}
#include<stdio.h>
int main()
{
int coins[10]={1,3,4},lookup[100000];
int i,j,tmp,num_coins = 3,sum=100;
lookup[0]=0;
for(i = 1; i <= sum; i++)
{
int min_coins = i;
for(j = 0;j < num_coins; j++)
{
tmp = i - coins[j];
if(tmp < 0)
continue;
if(lookup[tmp] < min_coins)
______________;
}
lookup[i] = min_coins + 1;
}
printf("%d",lookup[sum]);
return 0;
}100. What is the output of the following code?
#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 4, num_of_faces = 6, sum = 3;
int ans = get_ways(num_of_dice, num_of_faces, sum);
printf("%d",ans);
return 0;
}
#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
int arr[num_of_dice + 1][S + 1];
int dice, face, sm;
for(dice = 0; dice <= num_of_dice; dice++)
for(sm = 0; sm <= S; sm++)
arr[dice][sm] = 0;
for(sm = 1; sm <= S; sm++)
arr[1][sm] = 1;
for(dice = 2; dice <= num_of_dice; dice++)
{
for(sm = 1; sm <= S; sm++)
{
for(face = 1; face <= num_of_faces && face < sm; face++)
arr[dice][sm] += arr[dice - 1][sm - face];
}
}
return arr[num_of_dice][S];
}
int main()
{
int num_of_dice = 4, num_of_faces = 6, sum = 3;
int ans = get_ways(num_of_dice, num_of_faces, sum);
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.