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₁, P₂, P₃, P₄, P ₅} = {20, 15, 10, 5, 3} & {d₁, d₂, d₃, d₄, d₅} = {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)