Dynamic Programming in Data Structures
practice.

Which of the following is NOT a Catalan number?

Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1, -2, -1, 5, -4}

The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?

Consider the following dynamic programming implementation of the longest common subsequence problem:

#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])
                  ______________;
                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;
}

Which of the following lines completes the above code?

There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?

Consider the following dynamic programming implementation of the Knapsack problem:

#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] = ______________;
               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;
}

Which of the following lines completes the above code?

Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?

What is the space 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;
}

Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?

What is the value stored in ans[3][3] when the following code is executed?

#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;
}

For which of the following inputs would Kadane's algorithm produce the INCORRECT output?

Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?

#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] = _______________________;
      int mx = sum[0];
      for(idx = 0; idx < len; idx++)
	 if(sum[idx] > mx)
	     mx =sum[idx];
	 return mx;
}
int main()
{
      int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

Which of the following is/are property/properties of a dynamic programming problem?

What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?

Suppose you are given infinite coins of N denominations v1, v2, v3, ....., vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

What is the time complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

1. int fibo(int n)
2.	int fibo_terms[100000]  //arr to store the fibonacci numbers
3.	fibo_terms[0] = 0
4.	fibo_terms[1] = 1
5.		
6.	for i: 2 to n
7.		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
8.	
9.	return fibo_terms[n]

Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4

What is the minimum time required to build the car chassis?

You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?

What is the output of the following code?

#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,25,30,35,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}