Answer any one question from Q1 and Q2

1 (a)
Write the recurrence relation for binary search and solve it.

6 M

1 (b)
Explain the Greedy Prim's minimum spanning tree algorithm.

4 M

1 (c)
Write control abstraction for divide and conquer algorithmic strategy. Also write recurrence relation for the same.

5 M

1 (d)
Define asymptotic notations. Explain their significance in analyzing algorithms.

3 M

2 (a)
Write an algorithm for quick sort. State its time complexity.

6 M

2 (b)
Solve the following instance of 'job sequencing with deadlines' problem: n = 7, profits (p1, p2, p3, ........,p7) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d1, d2, ........., d7) = (1, 3, 4, 3, 2, 1, 2)

4 M

2 (c)
Obtain a set of optimal Huffman codes for the messages (M1, M2, ..... M6) with relative frequencies (q1, q2, ....... q6) = (2, 3, 5, 7, 9, 13). Draw the decode tree for this set of codes.

8 M

Answer any one question from Q3 and Q4

3 (a)
Let n = 3 and {k1, k2, k3} = {do, if, while} Let p (1:3) = {0.5, 0.1, 0.05} Let q (0:3} = {0.15, 0.1, 0.05, 0.05} Compute & construct OBST for above values.

9 M

3 (b)
State multistage graph problem and explain how it can be solved using forward approach.

7 M

4 (a)
Explain 0/1 Knapsack using dynamic programming with an example.

8 M

4 (b)
Define the Travelling Salesperson Problem. Solve the TSP problem using Dynamic programming where the edge lengths are given as:

0 | 9 | 8 | 8 |

12 | 0 | 13 | 6 |

10 | 9 | 0 | 5 |

20 | 15 | 10 | 0 |

8 M

Answer any one question from Q5 and Q6

5 (a)
What are implicit and explicit constraints with respect to backtracking?

8 M

5 (b)
Write the control abstraction for LC-Search. Explain how Travelling Salesperson problem is solved using LCBB.

8 M

6 (a)
Write recursive algorithm on Graph Colouring using Backtracking Strategy. Determine the time complexity of the same.

8 M

6 (b)
Write an iterative algorithm to solve n Queen's problem using backtracking methods. What is the time complexity of this algorithm?

8 M

Answer any one question from Q7 and Q8

7 (a)
Prove that vertex cover problem is NP complete.

9 M

7 (b)
Show that the sum of subsets problem is NP-Hard, given that Exact cover problem is NP-Hard.

9 M

8 (a)
What is meant by a problem 'reducing to' another problem? Prove that the clique decision problem reduces to node cover decision problem.

8 M

8 (b)
Explain NP-Hard scheduling problem with example. Also comment on the time complexity.

10 M

Answer any one question from Q9 and Q10

9 (a)
Write an algorithm for Odd-Even merge. Determine its time complexity.

8 M

9 (b)
Consider the following expression:

((7 - (21 / 3)) * 3) + ((9 * (10 - 8)) + 6) Explain how it can be evaluated parallel.

((7 - (21 / 3)) * 3) + ((9 * (10 - 8)) + 6) Explain how it can be evaluated parallel.

8 M

10 (a)
Explain how graph problems can be solved using parallel processors.

8 M

10 (b)
Explain in detail parallel MERGE sorting.

8 M

Answer any one question from Q11 and Q12

11 (a)
Explain Deadlock detection and avoidance algorithm.

8 M

11 (b)
What is meant by heuristic algorithms? Discuss any one heuristic search algorithm.

8 M

12 (a)
Explain convex hull algorithm. Comment on the time complexity.

8 M

12 (b)
Explain resource allocation algorithm for deadlock avoidance.

8 M

More question papers from Design & Analysis of Algorithms