## MCQs

Total Questions : 22 | Page 1 of 3 pages
Question 1. What is the space complexity of Kadane's algorithm?
1.    O(1)
2.    O(n)
3.    O(n2)
4.    None of the mentioned

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?
1.    O(n)
2.    O(m)
3.    O(m + n)
4.    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;}
1.    tmp_max = LIS[j].
2.    LIS[i] = LIS[j].
3.    LIS[j] = tmp_max
4.    tmp_max = LIS[i].
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 ______________
1.    Greedy algorithm
2.    2D dynamic programming
3.    1D dynamic programming
4.    Divide and conquer
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
1.    arr[row][k] "“ arr[k + 1][col] + mat[row "“ 1] * mat[k] * mat[col];
2.    arr[row][k] + arr[k + 1][col] "“ mat[row "“ 1] * mat[k] * mat[col];
3.    arr[row][k] + arr[k + 1][col] + mat[row "“ 1] * mat[k] * mat[col];
4.    arr[row][k] "“ arr[k + 1][col] "“ mat[row "“ 1] * mat[k] * mat[col];
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?
1.    O(1)
2.    O(logn)
3.    O(nlogn)
4.    O(n!)

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?
1.    O(1)
2.    O(n+m)
3.    O(mn)
4.    O(nlogm)

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
1.    t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i])
2.    t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+spent[1][i])
3.    t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1])
4.    none of the mentioned
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?
1.    4
2.    3
3.    5
4.    6

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
1.    find_max(ans[itm "“ 1][w "“ wt[itm "“ 1]] + val[itm "“ 1], ans[itm "“ 1][w])
2.    find_max(ans[itm "“ 1][w "“ wt[itm "“ 1]], ans[itm "“ 1][w])
3.    ans[itm][w] = ans[itm "“ 1][w];
4.    none of the mentioned
Answer: Option C. -> ans[itm][w] = ans[itm "“ 1][w];

find_max(ans[itm “ 1][w “ wt[itm “ 1]] + val[itm “ 1], ans[itm “ 1][w]) completes the above code.