MORE IN Analysis of Algorithms
MU Computer Engineering (Semester 4)
Analysis of Algorithms
May 2015
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) Write abstract algorithm for greedy design method.
5 M
1 (b) Which are different factors considered for sorting elements.
5 M
1 (c) Explain flow shop scheduling technique.
5 M
1 (d) Explain three cases of master theorem.
5 M

2 (a) Write and explain sum of subset algorithm for n=5, W={2,7,8,9,15} M=17.
10 M
2 (b) Explain randomized version of Quick sort and derive its complexity.
10 M

3 (a) Implement the bubble sort Algorithm and derive its best case and worst case complexity.
10 M
3 (b) Find the Huffman code for the following message.
"COLLEGE OF ENGINEERING"
10 M

4 (a) What is Hamiltonian cycle? Write an algorithm to find all Hamiltonian cycles.
10 M
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 M

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 M
5 (b) Explain naive string matching algorithm with example.
10 M

Write note on any two:
6 (a) Rabin karp algorithm
10 M
6 (b) 15-puzzle problem
10 M
6 (c) Travelling sales person problem.
10 M
6 (d) Strassen's matrix multiplication.
10 M

More question papers from Analysis of Algorithms