Question Paper: Analysis of Algorithms : Question Paper May 2015 - Computer Engineering (Semester 4) | Mumbai University (MU)
0

## 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, {P1, P2, P3, P4, P 5} = {20, 15, 10, 5, 3} & {d1, d2, d3, d4, d5} = {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)