## 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^{2}.(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_{1}, P_{2}, P_{3}, P_{4}, P_{5}]=[20, 15, 10, 5, 1] and

[d_{1}, d_{2}, d_{3}, d_{4}, d_{5}, = [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_{1}, W_{2}, W_{3}}={1, 2, 2} and {P_{1}, P_{2}, P_{3}}={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 (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 |

**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)