Dynamic Programming in Data Structures
practice.

Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}

In which of the following cases will the edit distance between two strings be zero?

What is the output of the following program?

#include<stdio.h>
#include<limits.h>
int min_jumps(int *arr, int strt, int end)
{
      int idx;
      if(strt == end)
 	 return 0;
      if(arr[strt] == 0) // jump cannot be made
	 return INT_MAX;
      int min = INT_MAX;
      for(idx = 1; idx <= arr[strt] && strt + idx <= end; idx++)
      {
	   int jumps = min_jumps(arr, strt + idx, end) + 1;
	   if(jumps < min)
	     min  = jumps;
      }
      return min;
}
int main()
{
      int arr[] ={1, 2, 3, 4, 5, 4, 3, 2, 1},len = 9;
      int ans = min_jumps(arr, 0, len-1);
      printf("%d\n",ans);
      return 0;
}

In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.

What is the time complexity of Kadane's algorithm?

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?

Longest common subsequence is an example of . . . . . . . .

What is the output of the following implementation of Kadane's algorithm?

#include<stdio.h>
int max_num(int a, int b)
{
       if(a > b)
	return a;
       return b;
}
int kadane_algo(int *arr, int len)	
{
       int ans, sum, idx;
       ans =0;
       sum =0;
       for(idx =0; idx < len; idx++)
       {
	     sum = max_num(0,sum + arr[idx]);
	     ans = max_num(sum,ans);
       }
       return ans;
}
int main()
{
      int arr[] = {2, 3, -3, -1, 2, 1, 5, -3}, len = 8;
      int ans = kadane_algo(arr,len);
      printf("%d",ans);
      return 0;
}

What is the time complexity of the brute force implementation of the maximum sum rectangle problem?

You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?

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

Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

What is the value stored in arr[3][3] when the below code is executed?

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

Consider a matrix in which all the elements are non-zero(at least one positive and at least one negative element). In this case, the sum of the elements of the maximum sum rectangle cannot be zero.

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

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

What is the space complexity of 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] == '|')
                  {
                      False[row][col] += False[row][pos] * False[pos+1][col];
                      True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col];;
                  }
                  if(op[pos] == '&')
                  {
                     True[row][col] += True[row][pos] * True[pos+1][col];
                     False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col];
                  }
                  if(op[pos] == '^')
                  {
                     True[row][col] += True[row][pos] * False[pos+1][col] 
                                       + False[row][pos] * True[pos + 1][col];
                     False[row][col] += True[row][pos] * True[pos+1][col] 
                                       + False[row][pos] * False[pos+1][col];
                  }
              }
          }
      }
      return True[0][str_len-1];
}

Which of the following methods can be used to solve the longest common subsequence problem?

Which of the following is not an application of Catalan Numbers?