Question 11. What is the output of the following code?#includeint 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;}

Question 12. What is the space complexity of the above dynamic programming implementation of the balanced partition problem?

Question 13. Consider the following dynamic programming implementation of the Boolean parenthesization problem: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];}Which of the following lines should be added to complete the "if(op[pos] == '|') part of the code?

Question 14. In dynamic programming, the technique of storing the previously calculated values is called ___________

Question 15. There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?

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

Question 17. 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 curFibComplete the above code.

Question 18. What is the output of the following naive method used to find the maximum sub-array sum?#includeint 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;}

Question 19. Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?

Question 20. What is the output of the following program?#includeint 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;}