Dynamic Programming in Data Structures
practice.

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

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

Consider the following code snippet:

1. int sum[len], idx;
2. sum[0] = arr[0];
3. for(idx = 1; idx < len; idx++)
4.	  sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx]);
5. int mx = sum[0];
6. for(idx = 0; idx < len; idx++)
7.	 if(sum[idx] > mx)
8.		mx =sum[idx];
9. return mx;

Which method is used by line 4 of the above code snippet?

What is the value stored in arr[2][2] when the following 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[] = "abcd", s2[] = "defg";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

Which of the following is an application of the edit distance problem?

The edit distance satisfies the axioms of a metric when the costs are non-negative.

Consider the following naive method to find the maximum sub-array sum:

#include<stdio.h>
int main()
{
     int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
     int cur_max, tmp_max, strt_idx, sub_arr_idx;
     cur_max = arr[0];
     for(strt_idx = 0; strt_idx < len; strt_idx++)
     {
	  tmp_max=0;
	  for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
	  {
	       tmp_max +=arr[sub_arr_idx];
	       if(tmp_max > cur_max)
		 _____________;
	  }
     }
     printf("%d",cur_max);
     return 0;
}

Which line should be inserted to complete the above code?

Consider the following code:

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

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

What is the output of the following code?

#include<stdio.h>
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
         arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}

Which of the following is not a palindromic subsequence of the string "ababcdabba"?

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] = {10,10,10,10,10,10};
     int ans = mat_chain_multiplication(mat,6);
     printf("%d",ans);
     return 0;
}

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

For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.

Which of the following methods can be used to solve the Knapsack problem?

Consider the following code:

#include<stdio.h>
int get_min(int a, int b)
{
     if(a<b)
        return a;
     return b;
}
int minimum_time_required(int reach[][3],int spent[][4], int *entry, int *exit, int n)
{
     int t1[n], t2[n],i;
     t1[0] = entry[0] + spent[0][0];
     t2[0] = entry[1] + spent[1][0];
     for(i = 1; i < n; i++)
     {
         t1[i] = get_min(t1[i-1]+spent[0][i], t2[i-1]+reach[1][i-1]+spent[0][i]);
         __________;
     }
     return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}

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

You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?

Consider the strings "monday" and "tuesday". What is the edit distance between the two strings?

Which of the following errors will occur when the below code is executed?

#include<stdio.h>
int cat_number(int n)
{
     int i,j,arr[n],k;
     arr[0] = 1;
     for(i = 1; i < n; i++)
     {
         arr[i] = 0;
         for(j = 0,k = i - 1; j < i; j++,k--)
           arr[i] += arr[j] * arr[k];
     }
     return arr[n-1];
}
int main()
{
     int ans, n = 100;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}

What is the output of the following code?

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

Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?

What is the time complexity of the recursive implementation used to find the nth fibonacci term?