Design and Analysis of Algorithms - Dec 2014

Computer Science Engg. (Semester 4)

TOTAL MARKS: 100
TOTAL TIME: 3 HOURS (1) Question 1 is compulsory.
(2) Attempt any four from the remaining questions.
(3) Assume data wherever required.
(4) Figures to the right indicate full marks. 1 (a) Find ged(31415, 14142) by applying Euclid's algorithm. Estimate how many times it is faster when compared to the algorithm based on consecutive integer checking.(4 marks) 1 (b) Compare the order growth of 1/2 n(n-1) and n².(4 marks) 1 (c) Explain the mathematical analysis of Fibonacci recursive algorithm.(6 marks) 1 (d) Write Brute force string matching algorithm.(6 marks) 2 (a) Find the upper bound of recurrences given below by substitution method. $$ \displaystyle i) \ 2T \left ( \dfrac {n}{2} \right )+n \\ ii) \ T\left ( \dfrac {n}{2} \right )+1 $$(6 marks) 2 (b) Sort the following elements using merge sort. Write the recursion tree.
70, 20, 30, 40, 10, 50, 60(6 marks) 2 (c) Write the algorithm for quick sort. Derive the worst case time efficiency of the algorithm.(8 marks) 3 (a) Write greedy method control abstraction for subset paradigm.(4 marks) 3 (b) Using greedy method, trace the following graph to get shortest path from vertex 'a' to all other vertices.
  (6 marks) 3 (c) What is the solution generated by the function job scheduling (JS) when n=5,
[P₁, P₂, P₃, P₄, P₅]=[20, 15, 10, 5, 1] and
[d₁, d₂, d₃, d₄, d₅, = [2, 2, 1, 3, 3](6 marks) 3 (d) Apply PRIMS algorithm for the following graph to find minimum spanning tree.
  (4 marks) 4 (a) Using dynamic programming, compute the shortest path from vertex 1 to all other vertices.
  (10 marks) 4 (b) Solve the Knapsack n=3, {W₁, W₂, W₃}={1, 2, 2} and {P₁, P₂, P₃}={18, 16, 6} and M=4 dynamic programming.(4 marks) 4 (c) For the given graph, obtain optimal cost tour using dynamic programming.
  (6 marks) 5 (a) What are the three variations of decrease and conquer technique.(3 marks) 5 (b) Conduct DFS for the following graph.