61. Consider the following dynamic programming implementation of the minimum jumps problem:
#include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
int j, idx, jumps[len];
jumps[len - 1] = 0;
for(idx = len - 2; idx >= 0; idx--)
{
int tmp_min = INT_MAX;
for(j = 1; j <= arr[idx] && idx + j < len; j++)
{
if(jumps[idx + j] + 1 < tmp_min)
tmp_min = jumps[idx + j] + 1;
}
jumps[idx] = tmp_min;
}
return jumps[0];
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
int ans = min_jump(arr,len);
printf("%d\n",ans);
return 0;
}
Which of the following "for" loops can be used instead of the inner for loop so that the output doesn't change?
#include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
int j, idx, jumps[len];
jumps[len - 1] = 0;
for(idx = len - 2; idx >= 0; idx--)
{
int tmp_min = INT_MAX;
for(j = 1; j <= arr[idx] && idx + j < len; j++)
{
if(jumps[idx + j] + 1 < tmp_min)
tmp_min = jumps[idx + j] + 1;
}
jumps[idx] = tmp_min;
}
return jumps[0];
}
int main()
{
int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
int ans = min_jump(arr,len);
printf("%d\n",ans);
return 0;
}62. What is the space complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int min_ins(char *s)
{
int len = strlen(s), i, j;
int arr[len + 1][len + 1];
char rev[len + 1];
strcpy(rev, s);
strrev(rev);
for(i = 0;i <= len; i++)
arr[i][0] = 0;
for(i = 0; i <= len; i++)
arr[0][i] = 0;
for(i = 1; i <= len; i++)
{
for(j = 1; j <= len; j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
return len - arr[len][len];
}
int main()
{
char s[] = "abcda";
int ans = min_ins(s);
printf("%d",ans);
return 0;
}
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int min_ins(char *s)
{
int len = strlen(s), i, j;
int arr[len + 1][len + 1];
char rev[len + 1];
strcpy(rev, s);
strrev(rev);
for(i = 0;i <= len; i++)
arr[i][0] = 0;
for(i = 0; i <= len; i++)
arr[0][i] = 0;
for(i = 1; i <= len; i++)
{
for(j = 1; j <= len; j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
return len - arr[len][len];
}
int main()
{
char s[] = "abcda";
int ans = min_ins(s);
printf("%d",ans);
return 0;
}63. Consider the following dynamic programming implementation of the matrix chain problem:
#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 = ________________________;
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?
#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 = ________________________;
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;
}64. What is the time complexity of the following dynamic programming implementation of the rod cutting problem?
#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;
}65. Consider the following dynamic programming implementation of the edit distance problem:
#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
_____________;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "abcd", s2[] = "defg";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}
Which of the following lines should be added to complete the above code?
#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
if(a < b)
return a;
return b;
}
int edit_distance(char *s1, char *s2)
{
int len1,len2,i,j,min;
len1 = strlen(s1);
len2 = strlen(s2);
int arr[len1 + 1][len2 + 1];
for(i = 0;i <= len1; i++)
arr[i][0] = i;
for(i = 0; i <= len2; i++)
arr[0][i] = i;
for(i = 1; i <= len1; i++)
{
for(j = 1; j <= len2; j++)
{
min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
if(s1[i - 1] == s2[j - 1])
{
if(arr[i-1][j-1] < min)
min = arr[i-1][j-1];
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1;
}
_____________;
}
}
return arr[len1][len2];
}
int main()
{
char s1[] = "abcd", s2[] = "defg";
int ans = edit_distance(s1, s2);
printf("%d",ans);
return 0;
}66. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
67. Which of the following problems is equivalent to the 0-1 Knapsack problem?
68. What is the value stored in arr[2][4] when the following code is executed?
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int min_ins(char *s)
{
int len = strlen(s), i, j;
int arr[len + 1][len + 1];
char rev[len + 1];
strcpy(rev, s);
strrev(rev);
for(i = 0;i <= len; i++)
arr[i][0] = 0;
for(i = 0; i <= len; i++)
arr[0][i] = 0;
for(i = 1; i <= len; i++)
{
for(j = 1; j <= len; j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
return len - arr[len][len];
}
int main()
{
char s[] = "abcda";
int ans = min_ins(s);
printf("%d",ans);
return 0;
}
#include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a;
return b;
}
int min_ins(char *s)
{
int len = strlen(s), i, j;
int arr[len + 1][len + 1];
char rev[len + 1];
strcpy(rev, s);
strrev(rev);
for(i = 0;i <= len; i++)
arr[i][0] = 0;
for(i = 0; i <= len; i++)
arr[0][i] = 0;
for(i = 1; i <= len; i++)
{
for(j = 1; j <= len; j++)
{
if(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1;
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]);
}
}
return len - arr[len][len];
}
int main()
{
char s[] = "abcda";
int ans = min_ins(s);
printf("%d",ans);
return 0;
}69. What is the space complexity of the following dynamic programming implementation of the maximum sum rectangle problem?
int max_sum_rectangle(int arr[][3],int row,int col)
{
int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
for(left = 0; left < col; left++)
{
for(right = left; right < col; right++)
{
if(right == left)
{
for(idx = 0; idx < row; idx++)
tmp[idx] = arr[idx][right];
}
else
{
for(idx = 0; idx < row; idx++)
tmp[idx] += arr[idx][right];
}
val = kadane_algo(tmp,row);
if(val > mx_sm)
mx_sm = val;
}
}
return mx_sm;
}
int max_sum_rectangle(int arr[][3],int row,int col)
{
int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
for(left = 0; left < col; left++)
{
for(right = left; right < col; right++)
{
if(right == left)
{
for(idx = 0; idx < row; idx++)
tmp[idx] = arr[idx][right];
}
else
{
for(idx = 0; idx < row; idx++)
tmp[idx] += arr[idx][right];
}
val = kadane_algo(tmp,row);
if(val > mx_sm)
mx_sm = val;
}
}
return mx_sm;
}70. Consider the following dynamic programming implementation of the boolean parenthesization problem:
int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
_______________;
}
if(op[pos] == '&')
{
_______________;
}
if(op[pos] == '^')
{
_______________;
}
}
}
}
return True[0][str_len-1];
}
Which of the following lines should be added to complete the "if(op[pos] == '|')" part of the code?
int count_bool_parenthesization(char *sym, char *op)
{
int str_len = strlen(sym);
int True[str_len][str_len],False[str_len][str_len];
int row,col,length,l;
for(row = 0, col = 0; row < str_len; row++,col++)
{
if(sym[row] == 'T')
{
True[row][col] = 1;
False[row][col] = 0;
}
else
{
True[row][col] = 0;
False[row][col] = 1;
}
}
for(length = 1; length < str_len; length++)
{
for(row = 0, col = length; col < str_len; col++, row++)
{
True[row][col] = 0;
False[row][col] = 0;
for(l = 0; l < length; l++)
{
int pos = row + l;
int t_row_pos = True[row][pos] + False[row][pos];
int t_pos_col = True[pos+1][col] + False[pos+1][col];
if(op[pos] == '|')
{
_______________;
}
if(op[pos] == '&')
{
_______________;
}
if(op[pos] == '^')
{
_______________;
}
}
}
}
return True[0][str_len-1];
}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.