## Analysis of Algorithms - May 2015

### 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)** Write abstract algorithm for greedy design method.(5 marks)
**1 (b)** Which are different factors considered for sorting elements.(5 marks)
**1 (c)** Explain flow shop scheduling technique.(5 marks)
**1 (d)** Explain three cases of master theorem.(5 marks)
**2 (a)** Write and explain sum of subset algorithm for n=5, W={2,7,8,9,15} M=17.(10 marks)
**2 (b)** Explain randomized version of Quick sort and derive its complexity.(10 marks)
**3 (a)** Implement the bubble sort Algorithm and derive its best case and worst case complexity.(10 marks)
**3 (b)** Find the Huffman code for the following message.

"COLLEGE OF ENGINEERING"(10 marks)
**4 (a)** What is Hamiltonian cycle? Write an algorithm to find all Hamiltonian cycles.(10 marks)
**4 (b)** Suppose your are given n number of coins, in that one coin is faulty. Its weight is less than standard coin weight. To find the faulty coin in a list using proper searching method. What will be the complexity of searching method.(10 marks)
**5 (a)** Explain Job sequencing with deadliner for the given instance.

n=5, {P_{1}, P_{2}, P_{3}, P_{4}, P _{5}} = {20, 15, 10, 5, 3} & {d_{1}, d_{2}, d_{3}, d_{4}, d_{5}} = {2, 2, 1, 3, 3}(10 marks)
**5 (b)** Explain naive string matching algorithm with example.(10 marks)

### Write note on any two:

**6 (a)** Rabin karp algorithm(10 marks)
**6 (b)** 15-puzzle problem(10 marks)
**6 (c)** Travelling sales person problem.(10 marks)
**6 (d)** Strassen's matrix multiplication.(10 marks)