Data Structure II Mock Test 7

1. What is the objective of the knapsack problem?

2. What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=n^c(log n)k?

3. Solve the following recurrence using Master’s theorem.
T(n) = 4 T (n/2) + n!

4. What is the space complexity of the recursive implementation used to find the nth fibonacci term?

5. Fill in the blank to complete the code.

#include<stdio.h>
int main()
{
      int coins[10]={1,3,4},lookup[100000];
      int i,j,tmp,num_coins = 3,sum=100;
      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)
	       ______________;
	   }
	   lookup[i] = min_coins + 1;
      }
      printf("%d",lookup[sum]);
      return 0;
}

6. What is the output of the following code?

#include<stdio.h>
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
        return i;
     return -1;
}
int main()
{
      int arr[5] ={1,3,3,3,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

7. When was the Eight Queen Puzzle published?

8. Who proposed the depth first backtracking algorithm?

9. What does the following code do?

#include<stdio.h>
int search_num(int *arr, int num, int len)
{
     int i;
     for(i = 0; i < len; i++)
     if(arr[i] == num)
      return i;
     return -1;
}
int main()
{
      int arr[5] ={1,2,3,4,5},num=3,len = 5;
      int indx = search_num(arr,num,len);
      printf("Index of %d is %d",num,indx);
      return 0;
}

10. 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 property is shown by line 7 of the above code?