Dynamic Programming in Data Structures
practice.

In Dynamic Programming, what does the term "subproblem" refer to?

Which problem is best solved using Dynamic Programming by maintaining a 2D table to store results?

What is the time complexity of the Dynamic Programming solution for the "Longest Palindromic Substring" problem?

How does the concept of "overlapping subproblems" apply to the "Knapsack Problem" in Dynamic Programming?

In the context of Dynamic Programming, what is the typical use of "backtracking"?

Consider the two strings ""(empty string) and "abcd". What is the edit distance between the two strings?

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

For which of the following pairs of strings is the edit distance maximum?

Consider the recursive implementation to find the nth fibonacci number:
Which line would make the implementation complete?

int fibo(int n)
    if n <= 1
	return n
    return __________

What is the time complexity of the brute force algorithm used to solve the balanced partition problem?

What will be the value stored in arr[5] when the following 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 = 10;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}

The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i).
Consider the following dynamic programming implementation for Catalan numbers:

#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--)
           ______________________;
     }
     return arr[n-1];
 
}
int main()
{
     int ans, n = 8;
     ans = cat_number(n);
     printf("%d\n",ans);
     return 0;
}

Which of the following lines completes the above code?

Wagner-Fischer is a . . . . . . . . algorithm.

Consider the following code snippet. Which property is shown by line 4 of the below 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;

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

Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?

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] = {20,30,40,50};
     int ans = mat_chain_multiplication(mat,4);
     printf("%d",ans);
     return 0;
}

Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}}
time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}}
entry_time[2] = {8, 10}
exit_time[2] = {10, 7}
num_of_stations = 4

For the optimal solution, which should be the exit assembly line?

Which of the following implementations of Catalan numbers has the largest space complexity(Don't consider the stack space)?

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