61. 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?
62. For every rod cutting problem there will be a unique set of pieces that give the maximum price.
63. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?
64. Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?
65. What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
66. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses . . . . . . . . property.
67. What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?
#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}
#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}68. Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?
69. You are given infinite coins of 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. This problem can be solved using . . . . . . . .
70. What is the output of the following code?
#include<stdio.h>
int get_min(int a, int b)
{
if(a<b)
return a;
return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
int t1[n], t2[n], i;
t1[0] = entry[0] + spent[0][0];
t2[0] = entry[1] + spent[1][0];
for(i = 1; i < n; i++)
{
t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
}
return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
int time_to_reach[][3] = {{6, 1, 5},
{2, 4, 7}};
int time_spent[][4] = {{6, 5, 4, 7},
{5, 10, 2, 6}};
int entry_time[2] = {5, 6};
int exit_time[2] = {8, 9};
int num_of_stations = 4;
int ans = minimum_time_required(time_to_reach, time_spent,
entry_time, exit_time, num_of_stations);
printf("%d",ans);
return 0;
}
#include<stdio.h>
int get_min(int a, int b)
{
if(a<b)
return a;
return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
int t1[n], t2[n], i;
t1[0] = entry[0] + spent[0][0];
t2[0] = entry[1] + spent[1][0];
for(i = 1; i < n; i++)
{
t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
}
return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
int time_to_reach[][3] = {{6, 1, 5},
{2, 4, 7}};
int time_spent[][4] = {{6, 5, 4, 7},
{5, 10, 2, 6}};
int entry_time[2] = {5, 6};
int exit_time[2] = {8, 9};
int num_of_stations = 4;
int ans = minimum_time_required(time_to_reach, time_spent,
entry_time, exit_time, num_of_stations);
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.