## Analysis of Algorithms - May 2013

### Computer Engineering (Semester 4)

TOTAL MARKS: 80

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **three** from the remaining questions.

(3) Assume data if required.

(4) Figures to the right indicate full marks.
**1 (a)** Explain Divide and Conquer strategy. Write control abstraction (general method) for it. List any four examples that can be solved by divide and conquer.(10 marks)
**1 (b)** Explain asymptotic notations. Explain time complexity and space complexity in detail.(10 marks)
**2 (a)** Explain Graph Colouring problem using backtracking. Write algorithm for same.(10 marks)
**2 (b)** Find out single source shortest path for following problem using Dijkstra's Algorithm.

(10 marks)

**3 (a)**Find the longest common subsequence from the given two sub-sequences:-

P = {100101101101}

Q = {0110}(10 marks)

**3 (b)**Explain 15 puzzle problem using Branch and Bound.(10 marks)

**4 (a)**Sort following numbers using Quicksort algorithm.

65, 70, 75, 80, 85, 60, 55, 50, 45.

Show all passes of execution. Also state the time complexity.(10 marks)

**4 (b)**Explain and write Knuth-Morris Pratt algorithm. Explain with an example.(10 marks)

**5 (a)**Explain job sequencing with deadlines. Solve the following instance: n=5

(P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1)(d1, d2, d3, d4, d5) = (2, 2, 1, 3, 3)(10 marks)

**5 (b)**Solve the following sum of subset problem using backtracking:

w= {1, 3, 4, 5}, m=8.

Find the possible subsets of 'w' that sum to 'm'.(10 marks)

**6 (a)**Solve shortest path from source 1 for following graph using dynamic programming.

(10 marks)

**6 (b)**Explain travelling Salesperson Problem using branch and bound method.(10 marks)

### Write short notes:-

**7 (a)** Differentiate between greedy approach and dynamic programming.(5 marks)
**7 (b)** Optimal Storage On Tapes(5 marks)
**7 (c)** Radix Sort(5 marks)
**7 (d)** Minimum Spanning Tree using Kruskal's algorithm.(5 marks)