## Design and Analysis of Algorithms - Dec 2013

### 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)** With the help of a flow chart. Explain the various steps of algorithm design and analysis process.(8 marks)
**1 (b)** If f_{1}(n) ∈ O(g_{1}(n)) and f_{2}(n) ∈ O(g_{2}(n)) prove that f_{1}(n)+f_{2}(n) ∈ O(max |g(n).g_{2}(n)|)(4 marks)
**1 (c)** Write an algorithm for selection sort and show that the time complexity of this algorithm is quadratic.(8 marks)
**2 (a)** What is divide and conquer method. Show that the worst case efficiency of binary search algorithm is 0 (log n).(10 marks)
**2 (b)** Explain quick sort algorithm. Find the time complexity of quick sort for best case, worst case and average case.(10 marks)
**3 (a)** Write Kruskal's algorithm to construct a minimum spanning tree and show that the time efficiency is O(|∈|log|&isi;|).(8 marks)
**3 (b)** Apply Kruskal's algorithm to find the min spanning tree of the graph.

(8 marks)
**3 (c)** Write Dijkstra's algorithm to find single source shortest path.(4 marks)
**4 (a)** Write the dynamic programming algorithm to computer binomial co-efficient and obtain its time complexity.(4 marks)
**4 (b)** Explain Warshall algorithm to find the transitive closure of a directed graph. Apply this algorithm to the graph given below.

(8 marks)
**4 (c)** State Floyd's algorithm. Solve all pairs shortest path problem for the given graph using Floyd algorithm.

(8 marks)
**5 (a)** Explain decrease and conquer method. With a suitable example.(4 marks)
**5 (b)** Apply the DFS-based algorithm to solve the topological sorting problem for given graph.

-(8 marks)
**5 (c)** State Horspool's algorithm for pattern matching. Apply the same to search for the pattern BARBER in a given text.(8 marks)
**6 (a)** Prove that the classic recursive algorithm for the tower of Hanoi puzzle makes the minimum number of disks moves needed to solve it.(8 marks)
**6 (b)** Write short notes on:

i) Tight lower bound

ii) Trivial lower bound

iii) Information theoretic lower bound.(12 marks)
**7 (a)** Explain how the TSP problem can be solved, using branch and bound method.(6 marks)
**7 (b)** Explain back-tracking concept and apply the same to n-queens problem(8 marks)
**7 (c)** Solve 8-queens problem for a feasible sequence (6, 4, 7, 1)(6 marks)
**8 (a)** Write short notes on:

i) Hamiltonian problem

ii) M- Colouring.(10 marks)
**8 (b)** Explain prefix computation problem and list ranking algorithm, with suitable examples.(10 marks)