• Attempt any five questions.
• All questions carry equal marks.
Solve the recurrence relation T(n)=1 for n≤4, T(n)=T(√n)+C for n>4 using substitution method.
Give an algorithm for quick sort and analyze the algorithm.
What is the solution generated by JS when n=7, P=(3,5,20,18,1,6,30), d=(1,3,4,3,2,1,2).
Show that adding an edge not in spanning tree T to T creates a unique cycle.
Find optimal solution for 0/1 knapsack problem: W=(10,15,6,9), P=(2,5,8,1), M=30.
How reliability design can be obtained using dynamic programming?
Generalize Hamiltonian so that it processes a graph with edge costs and finds a Hamiltonian cycle with minimum cost.
How can comparison trees be used for deriving lower bounds on problem of sorting.
Write a function to construct binary tree from given inorder and postorder sequences. What is the complexity?
Give an example of n-vertex graph where DFS recursion depth is n-1 but BFS queue has at most one vertex.
What do you mean by performance analysis of an algorithm? Explain.
Explain Heap? Sort the data using heap sort: 81,39,10,36,45,15,55,23,91,88,12.
Draw the portion of state space tree generated by LCBB for knapsack: n=4, P=(10,10,12,18), W=(2,4,6,9), M=15.
Give an example of knapsack instances for which |Sⁱ|=2ⁱ, 0≤i≤n.
Write short notes on (any two): a) Asymptotic Notations b) DFS and BFS c) Graph Coloring Problem.
