Dynamic Programming In Data Structures - Study Mode
[#186] You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
Correct Answer
(D) Brute force, Recursion and Dynamic Programming
[#187] What is the time 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)
[#188] Consider 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[][3],int spent[][4], 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])
__________
}
return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1])
} Which of the following lines should be inserted to complete the above code?
Correct Answer
(A) t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])
[#189] Which of the following errors will occur when the below code is executed? #include<stdio.h>
int cat_number(int n)
{
int i,j,arr[n],k
arr[0] = 1
for(i = 1
i < n
i++)
{
arr[i] = 0
for(j = 0,k = i - 1
j < i
j++,k--)
arr[i] += arr[j] * arr[k]
}
return arr[n-1]
}
int main()
{
int ans, n = 100
ans = cat_number(n)
printf("%d
",ans)
return 0
}
Correct Answer
(C) Integer value out of range
[#190] What is the output of the following code? #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
(D) 220