Dynamic Programming In Data Structures - Study Mode
[#231] What is the space complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n? #include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int lps(char *str1)
{
int i,j,len
len = strlen(str1)
char str2[len + 1]
strcpy(str2, str1)
strrev(str2)
int arr[len + 1][len + 1]
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(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1]
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1])
}
}
return arr[len][len]
}
int main()
{
char str1[] = "ababcdabba"
int ans = lps(str1)
printf("%d",ans)
return 0
}
Correct Answer
(C) O(n 2 )
[#232] Consider the following dynamic programming implementation of the longest common subsequence problem: #include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2
len1 = strlen(str1)
len2 = strlen(str2)
int arr[len1 + 1][len2 + 1]
for(i = 0
i <= len1
i++)
arr[i][0] = 0
for(i = 0
i <= len2
i++)
arr[0][i] = 0
for(i = 1
i <= len1
i++)
{
for(j = 1
j <= len2
j++)
{
if(str1[i-1] == str2[j - 1])
______________
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1])
}
}
return arr[len1][len2]
}
int main()
{
char str1[] = " abcedfg", str2[] = "bcdfh"
int ans = lcs(str1,str2)
printf("%d",ans)
return 0
} Which of the following lines completes the above code?
Correct Answer
(B) arr[i][j] = 1 + arr[i - 1][j - 1].
[#233] Consider 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] = ______________
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
} Which of the following lines completes the above code?
Correct Answer
(A) find_max(ans[itm - 1][w - wt[itm - 1]] + val[itm - 1], ans[itm - 1][w])
[#234] What is the space complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is "m" and the length of the other string is "n"? #include<stdio.h>
#include<string.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int lcs(char *str1, char *str2)
{
int i,j,len1,len2
len1 = strlen(str1)
len2 = strlen(str2)
int arr[len1 + 1][len2 + 1]
for(i = 0
i <= len1
i++)
arr[i][0] = 0
for(i = 0
i <= len2
i++)
arr[0][i] = 0
for(i = 1
i <= len1
i++)
{
for(j = 1
j <= len2
j++)
{
if(str1[i-1] == str2[j - 1])
arr[i][j] = 1 + arr[i - 1][j - 1]
else
arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1])
}
}
return arr[len1][len2]
}
int main()
{
char str1[] = " abcedfg", str2[] = "bcdfh"
int ans = lcs(str1,str2)
printf("%d",ans)
return 0
}
Correct Answer
(D) O(mn)
[#235] What is the time complexity of the following dynamic programming implementation of the Knapsack problem with n items and a maximum weight of W? #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)