Questions and answers for exam Preparation

MCQs

Total Questions : 22 | Page 1 of 3 pages

Question 1. What is the space complexity of Kadane's algorithm?

O(1)
O(n)
O(n2)
None of the mentioned

Discuss Question

Answer: Option A. -> O(1)

Kadane's algorithm uses a constant space. So, the space complexity is O(1).

Question 2. What is the time complexity of the above 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?

O(n)
O(m)
O(m + n)
O(mn)

Discuss Question

Answer: Option D. -> O(mn)

The time complexity of the above dynamic programming implementation of the longest common subsequence is O(mn).

Question 3. Complete the following dynamic programming implementation of the longest increasing subsequence problem:#includeint 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) ___________; } } 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;}

tmp_max = LIS[j].
LIS[i] = LIS[j].
LIS[j] = tmp_max
tmp_max = LIS[i].

Discuss Question

Answer: Option A. -> tmp_max = LIS[j].

tmp_max is used to store the maximum length of an increasing subsequence for any 'j' such that: arr[j] < arr[i] and 0 < j < i.
So, tmp_max = LIS[j] completes the code.

Question 4. Longest palindromic subsequence is an example of ______________

Greedy algorithm
2D dynamic programming
1D dynamic programming
Divide and conquer

Discuss Question

Answer: Option B. -> 2D dynamic programming

Longest palindromic subsequence is an example of 2D dynamic programming.

Question 5. Consider the following dynamic programming implementation of the matrix chain problem:#include#includeint mat_chain_multiplication(int *mat, int n){ int arr[n][n]; int i,k,row,col,len; for(i=1;i

arr[row][k] "“ arr[k + 1][col] + mat[row "“ 1] * mat[k] * mat[col];
arr[row][k] + arr[k + 1][col] "“ mat[row "“ 1] * mat[k] * mat[col];
arr[row][k] + arr[k + 1][col] + mat[row "“ 1] * mat[k] * mat[col];
arr[row][k] "“ arr[k + 1][col] "“ mat[row "“ 1] * mat[k] * mat[col];

Discuss Question

Answer: Option B. -> arr[row][k] + arr[k + 1][col] "“ mat[row "“ 1] * mat[k] * mat[col];

The line arr[row][k] + arr[k + 1][col] + mat[row “ 1] * mat[k] * mat[col] should be inserted to complete the above code.

Question 6. What is the space complexity of the ABOVE recursive implementation?

O(1)
O(logn)
O(nlogn)
O(n!)

Discuss Question

Answer: Option A. -> O(1)

The space complexity of the above recursive implementation is O(1) because it uses a constant space.

Question 7. What is the space complexity of the above implementation of Wagner“Fischer algorithm where "m and "n are the lengths of the two strings?

O(1)
O(n+m)
O(mn)
O(nlogm)

Discuss Question

Answer: Option C. -> O(mn)

The space complexity of the above Wagner“Fischer algorithm is O(mn).

Question 8. Consider the following code:#includeint get_min(int a, int b){ if(a

t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])
t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+spent[1][i])
t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1])
none of the mentioned

Discuss Question

Answer: Option A. -> t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])

The line t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]) should be added to complete the above code.

Question 9. You are given infinite coins of denominations 1, 3, 4. What is the total number of ways in which a sum of 7 can be achieved using these coins if the order of the coins is not important?

Discuss Question

Answer: Option C. -> 5

A sum of 7 can be achieved in the following ways:
{1,1,1,1,1,1,1}, {1,1,1,1,3}, {1,3,3}, {1,1,1,4}, {3,4}.
Therefore, the sum can be achieved in 5 ways.

Question 10. Consider the following dynamic programming implementation of the Knapsack problem:#includeint 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