Question Paper: Design and Analysis of Algorithms : Question Paper Dec 2014 - Computer Science Engg. (Semester 4) | Visveswaraya Technological University (VTU)
0

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 n2.(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,
[P1, P2, P3, P4, P5]=[20, 15, 10, 5, 1] and
[d1, d2, d3, d4, d5, = [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, {W1, W2, W3}={1, 2, 2} and {P1, P2, P3}={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.

(5 marks) 5 (c) Apply DFS based algorithm to solve topological sorting problem for the following graph:

(6 marks) 5 (d) Construct shift table for the pattern EARN and search for the same in text FAIL - MEANS - FIRST - ATTEMPT - IN - LEARNING using Horspool algorithm.(6 marks) 6 (a) Explain the four methods used to establish lower bounds of algorithm.(8 marks) 6 (b) Define decision trees. Write the decision tree for the three element selection sort.(6 marks) 6 (c) Define P, NP and NP complete problems.(6 marks) 7 (a) Explain how back tracking used for solving 4-queens problem. Write the state space tree.(6 marks) 7 (b) Solve the following assignment problem using branch and bound method.

 Job1 Job2 Job3 Job4 Person a 9 2 7 8 Person b 6 4 3 7 Person c 5 8 1 8 Person d 7 6 9 4
(8 marks)
7 (c) Apply twice-around-the-tree algorithm for the travelling sales person problem for the following graph.

(6 marks) 8 (a) Explain the various models for parallel computations.(9 marks) 8 (b) Let the i/p to the prefix computations be 5, 12, 8, 6, 3, 9, 11, 12, 1, 5, 6, 7, 10, 4, 3, 5 and three are four processors and ? stands for addition. With diagram explain how prefix computation is done by parallel algorithm.(8 marks) 8 (c) Explain how matrix M is computed using parallel algorithm for the given graph.

(3 marks)