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₁(n) ∈ O(g₁(n)) and f₂(n) ∈ O(g₂(n)) prove that f₁(n)+f₂(n) ∈ O(max |g(n).g₂(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)