Dynamic Programming in Data Structures
practice.

What is the output of 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);
      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[] = "abdgkagdjbccbba";
      int ans = lps(str1);
      printf("%d",ans);
      return 0;
}

What is the time complexity of 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 = 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,5,30,10,40};
     int ans = mat_chain_multiplication(mat,5);
     printf("%d",ans);
     return 0;
}

What is the space complexity of the following recursive implementation?

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
      if(a > b)
            return a;
      return b;
}
int rod_cut(int *prices, int len)
{
      int max_price = INT_MIN; // INT_MIN is the min value an integer can take
      int i;
      if(len <= 0 )
	return 0;
      for(i = 0; i < len; i++)
         // subtract 1 because index starts from 0
	 max_price = max_of_two(max_price, prices[i] + rod_cut(prices,len - i - 1)); 
      return max_price;
}
int main()
{
      int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
      int ans = rod_cut(prices, len_of_rod);
      printf("%d",ans);
      return 0;
}

The number of increasing subsequences with the longest length for the given sequence are:
{10, 9, 8, 7, 6, 5}

What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?

What is the time complexity of the following recursive implementation?

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
      if(a > b)
            return a;
      return b;
}
int rod_cut(int *prices, int len)
{
      int max_price = INT_MIN; // INT_MIN is the min value an integer can take
      int i;
      if(len <= 0 )
	return 0;
      for(i = 0; i < len; i++)
         // subtract 1 because index starts from 0
	 max_price = max_of_two(max_price, prices[i] + rod_cut(prices,len - i - 1)); 
      return max_price;
}
int main()
{
      int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 10;
      int ans = rod_cut(prices, len_of_rod);
      printf("%d",ans);
      return 0;
}

Kadane's algorithm uses which of the following techniques?

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

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

What is the value stored in arr[2][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 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[] = "hbcfgmnapq", str2[] = "cbhgrsfnmq";
      int ans = lcs(str1,str2);
      printf("%d",ans);
      return 0;
}

What will be the value stored in max_value when the following code is executed?

#include<stdio.h>
#include<limits.h>
int max_of_two(int a, int b)
{
       if(a > b)
         return a;
       return b;
}
int rod_cut(int *prices, int len)
{
       int max_price = INT_MIN; // INT_MIN is the min value an integer can take
       int i;
       if(len <= 0 )
          return 0;
       for(i = 0; i < len; i++)
          // subtract 1 because index starts from 0
          max_price = max_of_two(prices[i] + rod_cut(prices,len - i - 1), max_price); 
       return max_price;
}
int main()
{
       int prices[]={2, 5, 6, 9, 9, 17, 17, 18, 20, 22},len_of_rod = 3;
       int ans = rod_cut(prices, len_of_rod);
       printf("%d",ans);
       return 0;
}

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

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

Which of the following problems is NOT solved using dynamic programming?

What is the time complexity of the following dynamic programming algorithm used to find the maximum sub-array sum?

#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, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
      int ans = maximum_subarray_sum(arr, len);
      printf("%d",ans);
      return 0;
}

What is the output of the following code?

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

What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps?

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

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

Wagner-Fischer algorithm is used to find . . . . . . . .

What is the length of the longest palindromic subsequence for the string "ababcdabba"?

The Knapsack problem is an example of . . . . . . . .