Dynamic Programming In Data Structures - Study Mode
[#246] 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
}
Correct Answer
(A) True
[#247] 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.
Correct Answer
(A) max_price, prices[i] + rod_cut(prices,len - i - 1)
[#248] 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
}
Correct Answer
(A) True
[#249] 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
}
Correct Answer
(B) 1
[#250] 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
}
Correct Answer
(A) max_num(sum[idx - 1] + arr[idx], arr[idx])