Dynamic Programming in Data Structures
practice.

You are given a rod of length 10 and the following prices.

length     price
    1	           2
    2             5
    3	           6
    4	           9
    5	           9
    6	          17
    7 	          17	
    8	          18
    9	          20
   10	          22

Which of these pieces give the maximum price?

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

Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

What is the output of the following program?

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100];
      int i,j,tmp,num_coins = 3,sum=10;
      lookup[0]=0;
      for(i=1;i<=sum;i++)
      {
	    int min_coins = i;
	    for(j=0;j<num_coins;j++)
	    {
	         tmp=i-coins[j];
	         if(tmp<0)
	          continue;
	         if(lookup[tmp] < min_coins)
		 min_coins=lookup[tmp];
	    }
	    lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

You are given infinite coins of N 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. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?

Which of the following methods can be used to solve the assembly line scheduling problem?

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

What is the value stored in t1[2] when the following code is executed?

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

Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?

What is the value stored in t2[3] when the following code is executed?

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

What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?

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

You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?

What will be the output when the following code is executed?

#include<stdio.h>
int fibo(int n)
{
      int i;
      int fibo_terms[100];
      fibo_terms[0]=0;
      fibo_terms[1]=1;
      for(i=2;i<=n;i++)
          fibo_terms[i] = fibo_terms[i-2] + fibo_terms[i-1];
      return fibo_terms[n];
}
int main()
{
      int r = fibo(8);
      printf("%d",r);
      return 0;
}

Consider the following code to find 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
	   __________
  	   __________
       return curFib

Complete the above code.

Consider 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 = 0, sum = 0, idx;
    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;
}

What changes should be made to the Kadane's algorithm so that it produces the right output even when all array elements are negative?

Change 1 = Line 10: int sum = arr[0], ans = arr[0]
Change 2 = Line 13: sum = max_num(arr[idx],sum+arr[idx])

Which of the following methods can be used to solve the matrix chain multiplication problem?

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

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

For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.