a) Solve the following recurrence relations using the substitution method
$$T(n) = \begin{cases} 1 & n \le 4 \\ T(\sqrt{n}) + C & n > 4 \end{cases}$$ (Unit 1)

b) Give an algorithm for quick sort and analyze the algorithm. (Unit 1)

a) What is the solution generated by the function JS when $n = 7, (P_1, P_2, P_3, ......... P_7) = (3, 5, 20, 18, 1, 6, 30)$ and $(d_1, d_2, ......... d_7) = (1, 3, 4, 3, 2, 1, 2)$. (Unit 2)

b) Show that if $t$ is a spanning tree for the undirected graph G, then the addition of an edge $q, q \notin E(t)$ and $q \in E(G)$, to $t$ creates a unique cycle. (Unit 2)

a) Find optimal solution for 0/1 knapsack problem $(W_1, W_2, W_3, W_4) = (10, 15, 6, 9), (P_1, P_2, P_3, P_4) = (2, 5, 8, 1)$ and $M = 30$. (Unit 3)

b) How reliability design can be obtained using dynamic programming? (Unit 3)

a) Generalize Hamiltonian so that it processes a graph whose edges have costs associated with them and finds a Hamiltonian cycle with minimum cost. Assume that all edge costs are positive. (Unit 4)

b) How can comparison trees be used for deriving lower bounds on problem of sorting. (Unit 4)

a) Write a function to construct the binary tree with a given inorder sequence I and given postorder sequence P. What is the complexity of the function? (Unit 5)

b) Give an example of an n-vertex graph for which the depth of recursion of DFS starting from a particular vertex V is n-1 whereas the queue of BFS has at most one vertex at any given time, if BFS is started from the same vertex V. (Unit 5)

a) What do you mean by performance analysis of an algorithm? Explain. (Unit 1)

b) Explain Heap? Sort the following data using heap sort.
$81, 39, 10, 36, 45, 15, 55, 23, 91, 88, 12$ (Unit 1)

a) Draw the portion of state space tree generated by LCBB for following knapsack instance: $n = 4, (P_1, P_2, P_3, P_4) = (10, 10, 12, 18)$ and $(W_1, W_2, W_3, W_4) = (2, 4, 6, 9)$ and $M = 15$ (Unit 4)

b) Give an example of a set of knapsack instances for which $|S^i| = 2^i, 0 \le i \le n$. The set should include one instance for each $n$. (Unit 3)

Write short notes on following: (any two)

a) Asymptotic Notations (Unit 1)

b) DFS and BFS (Unit 5)

c) Graph Coloring Problem (Unit 4)