a) Write a recursive algorithm for computing the nth Fibonacci number. (Unit 1)

b) A machine needs a minimum of 200 sec to sort 1000 elements by Quick sort. What is the minimum time needed to sort 200 elements will be approximately? (Unit 1)

a) Generate recurrence relation from the recursive binary search algorithm. (Unit 1)

b) Consider the problem of finding the smallest and largest elements in an array of numbers using divide and Conquer method. (Unit 1)

a) Find the time complexity of the recurrence relation $T(n)=n+T(n/10)+T(7n/5)$. (Unit 1)

b) Analyze the time complexity of Strassen's algorithm compared to conventional matrix multiplication. (Unit 1)

a) What is Minimum Cost Spanning Tree? Explain Kruskal's Algorithm with the help of algorithm. (Unit 2)

b) The recurrence $T(n)=7T(n/2)+n2$ describe the running time of an algorithm A. A competing algorithm A has a running time of $\Gamma(n)=a\Gamma(n/4)+n2.$ What is the largest integer value for a A' is asymptotically faster than A? (Unit 1)

a) Explain properties of Binomial Heap in. Write an algorithm to perform uniting two Binomial Heaps. And also, to find Minimum Key. (Unit 1)

b) Explain Backtracking. Let set $S=\{1,3,4,5\}$ and $X=8$, we have to find subset sum problem using backtracking approach. (Unit 4)

a) What is stable sorting algorithm? Which of the sorting algorithms we have seen are stable and which are unstable? Give name with explanation. (Unit 1)

b) Suppose character a, b, c, d, e, f has probabilities 0.07, 0.09, 0.12, 0.22, 0.23, 0.27 respectively. Find an optional Huffman code and draw the Huffman tree. What is the average code length? (Unit 2)

a) Write Merge sort algorithm and sort the following sequence {23, 11, 5, 15, 68, 31, 4, 17} using merge sort. (Unit 1)

b) Explain B-Tree and its properties. Also write B-Tree deletion cases with example. (Unit 5)

a) For a binary tree T, the preorder and in-order traversal sequences are as follows:
In order : BCAEGDHFIJ
Preorder : ABCDEGFHIJ
i) Construct a binary Tree.
ii) What is its post-order traversal sequence? (Unit 5)

b) Prove that if the weights on the edge of the connected undirected graph are distinct then there is a unique Minimum Spanning Tree. Give an example in this regard. Also discuss Kruskal's Minimum Spanning Tree in detail. (Unit 2)