## Analysis of Algorithms - Dec 2012

### 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)** Arrange the following functions in increasing order

N, log n, n^{3}, n^{2}, nlogn, 2^{n}, n!(5 marks)
**1 (b)** Explain general method of dynamic programming. List different examples of it.(5 marks)
**1 (c)** Justify Greedy approach for solving knapsack problem.(5 marks)
**1 (d)** State Graph Colouring problem. State the strategy used to solve above problem.(5 marks)
**2 (a)** Sort the following numbers using Merge Sort-

27, 6, 18, 25, 48, 59, 98, 34.

Give the output of each pass. Write an algorithm for merge sort.(10 marks)
**2 (b)** Write an algorithm for minimum spanning tree using Prim^{'}s method.(10 marks)
**3 (a)** Explain N-Queen^{'}s problem using backtracking with algorithm.(10 marks)
**3 (b)** Consider the following set of frequencies

A=2, B=6, C=4, D=15, E=7, F=22, H=17

Find Huffman codes for the same.(10 marks)
**4 (a)** Describe 0/1 knapsack problem. How to solve it using branch and bound?(10 marks)
**4 (b)** Write an algorithm for binary search. Derive its best case and worst case complexities.(10 marks)
**5 (a)** For the following graph find all pairs shortest path using dynamic programming.

(10 marks)

**5 (b)**Explain optimal storage on tapes.(10 marks)

**6 (a)**Find longest subsequence of given two steps

X = {B A T A}

Y = {T A T A}(10 marks)

**6 (b)**Explain single source shortest path using dynamic programming. Write an algorithm for the same.(10 marks)

### Write short notes on the following :-

**7 (a)** Radix Sort(5 marks)
**7 (b)** Job Sequencing with Deadline(5 marks)
**7 (c)** Strassens Multiplication(5 marks)
**7 (d)** Branch and Bound Strategy(5 marks)