Dynamic Programming in Data Structures
practice.

Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?

For every rod cutting problem there will be a unique set of pieces that give the maximum price.

In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?

Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses . . . . . . . . property.

What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

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

Consider the following array:
{1, 3, 5, 8, 9, 2, 6, 7, 6}
What is the minimum number of jumps required to reach the end of the array?

You are given infinite coins of denominations v1, v2, v3, ....., vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using . . . . . . . .

What is the output of 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]);
         t2[i] = get_min(t2[i-1]+spent[1][i], t1[i-1]+reach[0][i-1]+spent[1][i]);
     }
     return get_min(t1[n-1]+exit[0], t2[n-1]+exit[1]);
}
int main()
{
    int time_to_reach[][3] = {{6, 1, 5},
                           {2, 4, 7}};
    int time_spent[][4] = {{6, 5, 4, 7},
                        {5, 10, 2, 6}};
    int entry_time[2] = {5, 6};
    int exit_time[2] = {8, 9};
    int num_of_stations = 4;
    int ans = minimum_time_required(time_to_reach, time_spent, 
              entry_time, exit_time, num_of_stations);
    printf("%d",ans);
    return 0;
}

Which of the following implementations of Catalan numbers has the smallest time complexity?

The longest increasing subsequence problem is a problem to find the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and it's length is maximum. This problem can be solved using . . . . . . . .

What is the space complexity of the following for loop method used to compute the nth fibonacci term?

int fibo(int n)
    if n == 0
       return 0 
    else
       prevFib = 0
       curFib = 1
       for i : 1 to n-1
           nextFib = prevFib + curFib
	   prevFib = curFib
           curFib = nextFib
       return curFib

The 0-1 Knapsack problem can be solved using Greedy algorithm.

Consider a variation of the balanced partition problem in which we find two subsets such that |S1 - S2| is minimum. Consider the array {1, 2, 3, 4, 5}. Which of the following pairs of subsets is an optimal solution for the above problem?

Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?

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

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping subproblems.

Consider the string "efge". What is the minimum number of insertions required to make the string a palindrome?

Consider the following statements and select which of the following statement are true.
Statement 1: The maximum sum rectangle can be 1X1 matrix containing the largest element If the matrix size is 1X1
Statement 2: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are zero
Statement 3: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are negative