Dynamic Programming in Data Structures
practice.

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

Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?

In which of the following cases, it is not possible to have two subsets with equal sum?

Which of the following numbers is the 6th Catalan number?

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

In which of the following cases, the maximum sum rectangle is the 2D matrix itself?

What is the time complexity of the following dynamic programming implementation of the Knapsack problem with n items and a maximum weight of W?

#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] = find_max(ans[itm - 1][w-wt[itm - 1]]+val[itm - 1], ans[itm - 1][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;
}

What is the output of the following code?

#include<stdio.h>
#include<string.h>
int get_min(int a, int b)
{
      if(a < b)
        return a;
      return b;
}
int edit_distance(char *s1, char *s2)
{
      int len1,len2,i,j,min;
      len1 = strlen(s1);
      len2 = strlen(s2);
      int arr[len1 + 1][len2 + 1];
      for(i = 0;i <= len1; i++)
         arr[i][0] = i;
      for(i = 0; i <= len2; i++)
         arr[0][i] = i;
      for(i = 1; i <= len1; i++)
      {
          for(j = 1; j <= len2; j++)
          {
               min = get_min(arr[i-1][j],arr[i][j-1]) + 1;
               if(s1[i - 1] == s2[j - 1])
               {
                   if(arr[i-1][j-1] < min)
                      min = arr[i-1][j-1];
               }
               else
               {
                   if(arr[i-1][j-1] + 1 < min)
                     min = arr[i-1][j-1] + 1;
               }
               arr[i][j] = min;
          }
      }
      return arr[len1][len2];
}
int main()
{
      char s1[] = "somestring", s2[] = "anotherthing";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

What will be the output when the following code is executed?

#include<stdio.h>
int fibo(int n)
{
      if(n==0)
         return 0;
      int i;
      int prevFib=0,curFib=1;
      for(i=1;i<=n-1;i++)
      {
           int nextFib = prevFib + curFib;
	   prevFib = curFib;
           curFib = nextFib;
      }
      return curFib;
}
int main()
{
      int r = fibo(10);  
      printf("%d",r);
      return 0;
}

Consider the following dynamic programming implementation:

#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 _____________;
}
int main()
{
      char s[] = "abcda";
      int ans = min_ins(s);
      printf("%d",ans);
      return 0;
}

Which of the following lines should be added to complete the code?

Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?

What is the output of the following program?

#include<stdio.h>
#include<limits.h>
int rod_cut(int *prices, int len)
{
      int max_val[len + 1];
      int i,j,tmp_price,tmp_idx;
      max_val[0] = 0;
      for(i = 1; i <= len; i++)
      {
	   int tmp_max = INT_MIN; // minimum value an integer can hold
	   for(j = 1; j <= i; j++)
	   {
	        tmp_idx = i - j;
                //subtract 1 because index of prices starts from 0
	        tmp_price = prices[j-1] + max_val[tmp_idx];
	        if(tmp_price > tmp_max)
		  tmp_max = tmp_price;
	   }
	   max_val[i] = tmp_max;
      }
      return max_val[len];
}
int main()
{
      int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 5;
      int ans = rod_cut(prices, len_of_rod);
      printf("%d",ans);
      return 0;
}

Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8)
fibonacci(7) + fibonacci(6)
fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) 
+ fibonacci(3)	+ fibonacci(3) + fibonacci(2)
:
:
:

Which property is shown by the above function calls?

Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?

What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?

What is the output of the following program?

#include<stdio.h>
int fibo(int n)
{
      if(n<=1)
	 return n;
      return fibo(n-1) + fibo(n-2);
}
int main()
{   
      int r = fibo(50000);
      printf("%d",r); 
      return 0;
}

For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.

You are given a rod of length 5 and the prices of each length are as follows:

length     price
    1	           2
    2	           5
    3	           6
    4	           9
    5	           9

What is the maximum value that you can get after cutting the rod and selling the pieces?

Fill in the blank to complete the code.

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100000];
      int i,j,tmp,num_coins = 3,sum=100;
      lookup[0]=0;
      for(i = 1; i <= sum; i++)
      {
	   int min_coins = i;
	   for(j = 0;j < num_coins; j++)
	   {
	        tmp = i - coins[j];
	        if(tmp < 0)
	         continue;
	        if(lookup[tmp] < min_coins)
	       ______________;
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

What is the output of the following code?

#include<stdio.h>
int get_ways(int num_of_dice, int num_of_faces, int S)
{
     int arr[num_of_dice + 1][S + 1];
     int dice, face, sm;
     for(dice = 0; dice <= num_of_dice; dice++)
         for(sm = 0; sm <= S; sm++)
           arr[dice][sm] = 0;
     for(sm = 1; sm <= S; sm++)
         arr[1][sm] = 1;
     for(dice = 2; dice <= num_of_dice; dice++)
     {
         for(sm = 1; sm <= S; sm++)
         {
             for(face = 1; face <= num_of_faces && face < sm; face++)
                 arr[dice][sm] += arr[dice - 1][sm - face];
         }
     }
     return arr[num_of_dice][S];
}
int main()
{
     int num_of_dice = 4, num_of_faces = 6, sum = 3;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}