Dynamic Programming in Data Structures
practice.

What is the output of the following code?

#include<stdio.h>
#include<limits.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 max_sum_rectangle(int arr[][5],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;
}
int main()
{
       int arr[2][5] ={{1, 2, -1, -4, -20}, {-4, -1, 1, 7, -6}};
       int row = 2, col = 5;
       int ans = max_sum_rectangle(arr,row,col);
       printf("%d",ans);
       return 0;
}

What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term?

int fibo(int n)
        int fibo_terms[100000]  //arr to store the fibonacci numbers
        fibo_terms[0] = 0
	fibo_terms[1] = 1
 
	for i: 2 to n
		fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
 
	return fibo_terms[n]

Longest palindromic subsequence is an example of . . . . . . . .

What is the output of 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] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
         }
     }
     return ans[sm/2][len];
}
int main()
{
     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 9;
     int ans = balanced_partition(arr,len);
     if(ans == 0)
       printf("false");
     else
       printf("true");
     return 0;
}

In which of the following cases the minimum no of insertions to form palindrome is maximum?

Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?

Find the maximum sub-array sum for the following array:
{3, 6, 7, 9, 3, 8}

You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?

If a problem can be broken into subproblems which are reused several times, the problem possesses . . . . . . . . property.

Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?

What is the space complexity of the following dynamic programming implementation of the edit distance problem where "m" and "n" are the lengths of the two strings?

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

What is the value stored in max_val[5] after the following program is executed?

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

What is the output of the following code?

#include<stdio.h>
#include<string.h>
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];
}
int main()
{
     char sym[] = "TTTT";
     char op[] = "|^^";
     int ans = count_bool_parenthesization(sym,op);
     printf("%d",ans);
     return 0;
}

What is the output of the following naive method used to find the maximum sub-array sum?

#include<stdio.h>
int main()
{
     int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, 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)
	        cur_max = tmp_max;
	   }
     }
     printf("%d",cur_max);
     return 0;
}

Complete the following dynamic programming implementation of the longest increasing subsequence problem:

#include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
      int i, j, tmp_max;
      int LIS[len];  // array to store the lengths of the longest increasing subsequence 
      LIS[0]=1;
      for(i = 1; i < len; i++)
      { 
           tmp_max = 0;
	   for(j = 0; j < i; j++)
	   {
	        if(arr[j] < arr[i])
	        {
		    if(LIS[j] > tmp_max)
		     ___________;  
	        }
           }
	   LIS[i] = tmp_max + 1;
      }
      int max = LIS[0];
      for(i = 0; i < len; i++)
	if(LIS[i] > max)
	   max = LIS[i];
      return max;
}
int main()
{
      int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9;
      int ans = longest_inc_sub(arr, len);
      printf("%d",ans);
      return 0;
}

Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called . . . . . . . .

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 technique is used by line 7 of the above code?

What is the output of the following program?

#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[] = {-20, 23, 10, 3, -10, 11, -5},len = 7;
     int ans = maximum_subarray_sum(arr, len);
     printf("%d",ans);
     return 0;
}

The following sequence is a fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, ....
Which technique can be used to get the nth fibonacci term?