Dynamic Programming In Data Structures - Study Mode
[#271] What is the time complexity of the following dynamic programming implementation of the edit distance problem where "m" and "n" are the lengths of two strings? #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
}
arr[i][j] = min
}
}
return arr[len1][len2]
}
int main()
{
char s1[] = "abcd", s2[] = "defg"
int ans = edit_distance(s1, s2)
printf("%d",ans)
return 0
}
Correct Answer
(C) O(mn)
[#272] What is the output of the following program? #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[] ={9, 9, 9, 9, 9, 9, 9, 9, 9},len = 9
int ans = min_jump(arr,len)
printf("%d
",ans)
return 0
}
Correct Answer
(A) 1
[#273] What is the space complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence? #include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max
int LIS[len]
// array to store the lengths of the longest increasing subsequence
LIS[0]=1
for(i = 1
i < len
i++)
{
tmp_max = 0
for(j = 0
j < i
j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j]
}
}
LIS[i] = tmp_max + 1
}
int max = LIS[0]
for(i = 0
i < len
i++)
if(LIS[i] > max)
max = LIS[i]
return max
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9
int ans = longest_inc_sub(arr, len)
printf("%d",ans)
return 0
}
Correct Answer
(B) O(n)
[#274] Consider the following recursive implementation: #include<stdio.h>
#include<limits.h>
int min_jumps(int *arr, int strt, int end)
{
int idx
if(strt == end)
return 0
if(arr[strt] == 0) // jump cannot be made
return INT_MAX
int min = INT_MAX
for(idx = 1
idx <= arr[strt] && strt + idx <= end
idx++)
{
int jumps = min_jumps(____,____,____) + 1
if(jumps < min)
min = jumps
}
return min
}
int main()
{
int arr[] ={1, 3, 5, 8, 9, 2, 6, 7, 6},len = 9
int ans = min_jumps(arr, 0, len-1)
printf("%d
",ans)
return 0
} Which of these arguments should be passed by the min_jumps function represented by the blanks?
Correct Answer
(A) arr, strt + idx, end
[#275] What is the output of the following code? #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[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq"
int ans = lcs(str1,str2)
printf("%d",ans)
return 0
}
Correct Answer
(B) 4