Dynamic Programming in Data Structures MCQ question and answer with solution

Home / Data Structure / Dynamic Programming In Data Structures

3.
What is the output of the following program?
#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;
}

Answer & Solution Discuss in Board Save for Later

4.
What is the value stored in sum[4] after the following program is executed?
#include<stdio.h>
int max_num(int a,int b)
{
      if(a> b)
	  return a;
      return b;
}
int maximum_subarray_sum(int *arr, int len)
{
      int sum[len], idx;
      sum[0] = arr[0];
      for(idx = 1; idx < len; idx++)
	   sum[idx] = max_num(sum[idx - 1] + arr[idx], arr[idx]);
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	  if(sum[idx] > mx)
	      mx =sum[idx];
      return mx;
}
int main()
{
      int arr[] = {-2, 14, 11, -13, 10, -5, 11, -6, 3, -5},len = 10;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

Answer & Solution Discuss in Board Save for Later

5.
What is the value stored in arr[3][3] when the following code is executed?
#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[] = "ababcdabba";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

Answer & Solution Discuss in Board Save for Later

6.
What is the time complexity of the following dynamic programming implementation of the balanced partition problem where "n" is the number of elements and "sum" is their sum?
#include<stdio.h>
int balanced_partition(int *arr, int len)
{
     int sm = 0, i, j;
     for(i = 0;i < len; i++)
      sm += arr[i];
     if(sm % 2 != 0)
        return 0;
     int ans[sm/2 + 1][len + 1];
     for(i = 0; i <= len; i++)
      ans[0][i] = 1;
     for(i = 1; i <= sm/2; i++)
      ans[i][0] = 0;
     for(i = 1; i <= sm/2; i++)
     {
         for(j = 1;j <= len; j++)
         {
             ans[i][j] = ans[i][j-1];
             if(i >= arr[j - 1])
                ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

Answer & Solution Discuss in Board Save for Later

9.
Consider the following code snippet:
int max_sum_rectangle(int arr[][3],int row,int col)
{
      int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
      for(left = 0; left < col; left++)
      {
           for(right = left; right < col; right++)
           {
               if(right == left)
               {
                   for(idx = 0; idx < row; idx++)
                     tmp[idx] = arr[idx][right];
               }
               else
               {
                   for(idx = 0; idx < row; idx++)
                      tmp[idx] += arr[idx][right];
               }
               val = kadane_algo(tmp,row);
               if(val > mx_sm)
                  ______;
           }
      }
      return mx_sm;
}
Which of the following lines should be inserted to complete the above code?

Answer & Solution Discuss in Board Save for Later

10.
What is the space complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?
#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[] = "ababcdabba";
     int ans = lps(str1);
     printf("%d",ans);
     return 0;
}

Answer & Solution Discuss in Board Save for Later

Read More Section(Dynamic Programming in Data Structures)

Each Section contains maximum 100 MCQs question on Dynamic Programming in Data Structures. To get more questions visit other sections.