Dynamic Programming In Data Structures - Study Mode
[#276] Consider the following implementation of the Wagner-Fischer algorithm: 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)
____________
}
else
{
if(arr[i-1][j-1] + 1 < min)
min = arr[i-1][j-1] + 1
}
arr[i][j] = min
}
}
return arr[len1][len2]
} Which of the following lines should be inserted to complete the above code?
Correct Answer
(C) min = arr[i-1][j-1].
[#277] 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[][4],int spent[][5], 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[][4] = {{16, 10, 5, 12},
{12, 4, 17, 8}}
int time_spent[][5] = {{13, 5, 20, 19, 9},
{15, 10, 12, 16, 13}}
int entry_time[2] = {12, 9}
int exit_time[2] = {10, 13}
int num_of_stations = 5
int ans = minimum_time_required(time_to_reach, time_spent,
entry_time, exit_time, num_of_stations)
printf("%d",ans)
return 0
}
Correct Answer
(D) 88
[#278] What is the space complexity of the following dynamic programming implementation of the Knapsack problem? #include<stdio.h>
int find_max(int a, int b)
{
if(a > b)
return a
return b
}
int knapsack(int W, int *wt, int *val,int n)
{
int ans[n + 1][W + 1]
int itm,w
for(itm = 0
itm <= n
itm++)
ans[itm][0] = 0
for(w = 0
w <= W
w++)
ans[0][w] = 0
for(itm = 1
itm <= n
itm++)
{
for(w = 1
w <= W
w++)
{
if(wt[itm - 1] <= w)
ans[itm][w] = find_max(ans[itm - 1][w - wt[itm - 1]]+val[itm - 1], ans[itm - 1][w])
else
ans[itm][w] = ans[itm - 1][w]
}
}
return ans[n][W]
}
int main()
{
int w[] = {10,20,30}, v[] = {60, 100, 120}, W = 50
int ans = knapsack(W, w, v, 3)
printf("%d",ans)
return 0
}
Correct Answer
(C) O(nW)
[#279] What is the output of the following code? #include<stdio.h>
#include<limits.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int kadane_algo(int *arr, int len)
{
int ans, sum, idx
ans =0
sum =0
for(idx =0
idx < len
idx++)
{
sum = max_num(0,sum + arr[idx])
ans = max_num(sum,ans)
}
return ans
}
int max_sum_rectangle(int arr[][5],int row,int col)
{
int left, right, tmp[row], mx_sm = INT_MIN, idx, val=0
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 main()
{
int arr[4][5] ={{ 7, 1, -3, -6, -15},
{ 10, -6, 3, -4, 11},
{ -2, -3, -1, 2, -5},
{ 3, 0, 1, 0, 3}}
int row = 4, col = 5
int ans = max_sum_rectangle(arr,row,col)
printf("%d",ans)
return 0
}
Correct Answer
(B) 18
[#280] What is the output of the following program? #include<stdio.h>
int main()
{
int coins[10]={1,3,4},lookup[100]
int i,j,tmp,num_coins = 3,sum=14
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)
min_coins=lookup[tmp]
}
lookup[i] = min_coins + 1
}
printf("%d",lookup[sum])
return 0
}
Correct Answer
(C) 4