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"

"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, {P

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 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