Dynamic Programming in Data Structures
practice.

Consider the following dynamic programming implementation of the minimum jumps problem:

#include<stdio.h>
#include<limits.h>
int min_jump(int *arr, int len)
{
     int j, idx, jumps[len];
     jumps[len - 1] = 0;
     for(idx = len - 2; idx >= 0; idx--)
     {
	  int tmp_min = INT_MAX;
	  for(j = 1; j <= arr[idx] && idx + j < len; j++)
	  {
		 if(jumps[idx + j] + 1 < tmp_min)
		     tmp_min = jumps[idx + j] + 1;
	  }
	  jumps[idx] = tmp_min;
     }
     return jumps[0];
}
int main()
{
      int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9;
      int ans = min_jump(arr,len);
      printf("%d\n",ans);
      return 0;
}

Which of the following "for" loops can be used instead of the inner for loop so that the output doesn't change?

What is the space complexity of the following dynamic programming implementation of the minimum number of insertions to form a palindrome problem?

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

Consider the following dynamic programming implementation of the matrix chain problem:

#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 = ________________________;
                    if(tmp < arr[row][col])
                    arr[row][col] = tmp;
               }
           }
      }
      return arr[1][n - 1];
}
int main()
{
     int mat[6] = {20,5,30,10,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be inserted to complete the above code?

What is the time complexity of the following dynamic programming implementation of the rod cutting problem?

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

Consider the following dynamic programming implementation of the edit distance problem:

#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;
               }
                _____________;
         }
     }
     return arr[len1][len2];
}
int main()
{
     char s1[] = "abcd", s2[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

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

Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?

Which of the following problems is equivalent to the 0-1 Knapsack problem?

What is the value stored in arr[2][4] when the following code is executed?

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

What is the space complexity of the following dynamic programming implementation of the maximum sum rectangle problem?

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)
                 mx_sm = val;
           }
      }
      return mx_sm;
}

Consider the following dynamic programming implementation of the boolean parenthesization problem:

int count_bool_parenthesization(char *sym, char *op)
{
      int str_len = strlen(sym);
      int True[str_len][str_len],False[str_len][str_len];
      int row,col,length,l;
      for(row = 0, col = 0; row < str_len; row++,col++)
      {
          if(sym[row] == 'T')
          {
              True[row][col] = 1;
              False[row][col] = 0;
          }
          else
          {
              True[row][col] = 0;
              False[row][col] = 1;
          }
      }
      for(length = 1; length < str_len; length++)
      {
          for(row = 0, col = length; col < str_len; col++, row++)
          {
              True[row][col] = 0;
              False[row][col] = 0;
              for(l = 0; l < length; l++)
              {
                  int pos = row + l;
                  int t_row_pos = True[row][pos] + False[row][pos];
                  int t_pos_col = True[pos+1][col] + False[pos+1][col];
                  if(op[pos] == '|')
                  {
                      _______________;
                  }
                  if(op[pos] == '&')
                  {
                      _______________;
                  }
                  if(op[pos] == '^')
                  {
                      _______________;
                  }
              }
          }
      }
      return True[0][str_len-1];
}

Which of the following lines should be added to complete the "if(op[pos] == '|')" part of the code?

You are given infinite coins of denominations 3, 5, 7. Which of the following sum CANNOT be achieved using these coins?

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[] = "pqrstuv", s2[] = "prstuv";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

What is time complexity of the following dynamic programming implementation of the dice throw problem where f is the number of faces, n is the number of dice and s is the sum to be found?

#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 = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

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

Consider the following code:

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

Which of the following lines completes the above code?

Kadane's algorithm is used to find . . . . . . . .

Consider the following code to find the nth fibonacci term using dynamic programming:

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]

Which property is shown by line 7 of the above code?

You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem?

Which of the following is the longest common subsequence between the strings "hbcfgmnapq" and "cbhgrsfnmq" ?

Consider the following dynamic programming implementation of the dice throw problem:

#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 _____________;
}
int main()
{
     int num_of_dice = 3, num_of_faces = 4, sum = 6;
     int ans = get_ways(num_of_dice, num_of_faces, sum);
     printf("%d",ans);
     return 0;
}

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