Dynamic Programming In Data Structures - Study Mode
[#191] 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 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[] = "abdgkagdjbccbba"
int ans = lps(str1)
printf("%d",ans)
return 0
}
Correct Answer
(C) 9
[#192] What is the time complexity of the following dynamic programming implementation of the matrix chain problem? #include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n]
int i,k,row,col,len
for(i=1
i<n
i++)
arr[i][i] = 0
for(len = 2
len < n
len++)
{
for(row = 1
row <= n - len + 1
row++)
{
col = row + len - 1
arr[row][col] = INT_MAX
for(k = row
k <= col - 1
k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]
if(tmp < arr[row][col])
arr[row][col] = tmp
}
}
}
return arr[1][n - 1]
}
int main()
{
int mat[6] = {20,5,30,10,40}
int ans = mat_chain_multiplication(mat,5)
printf("%d",ans)
return 0
}
Correct Answer
(D) O(n 3 )
[#193] What is the space complexity of the following recursive implementation? #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++)
// subtract 1 because index starts from 0
max_price = max_of_two(max_price, prices[i] + rod_cut(prices,len - i - 1))
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
}
Correct Answer
(A) O(1)
[#194] What is the time complexity of the following recursive implementation? #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++)
// subtract 1 because index starts from 0
max_price = max_of_two(max_price, prices[i] + rod_cut(prices,len - i - 1))
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
}
Correct Answer
(D) O(2 n )
[#195] What is the time complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem? #include<stdio.h>
#include<string.h>
int max(int a, int b)
{
if(a > b)
return a
return b
}
int min_ins(char *s)
{
int len = strlen(s), i, j
int arr[len + 1][len + 1]
char rev[len + 1]
strcpy(rev, s)
strrev(rev)
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(s[i - 1] == rev[j - 1])
arr[i][j] = arr[i - 1][j - 1] + 1
else
arr[i][j] = max(arr[i - 1][j], arr[i][j - 1])
}
}
return len - arr[len][len]
}
int main()
{
char s[] = "abcda"
int ans = min_ins(s)
printf("%d",ans)
return 0
}
Correct Answer
(C) O(n 2 )