Answer any one question from Q1 and Q2

1 (a)
Give Greedy Prim's minimum spanning tree algorithm. Also explain it with suitable example.

10 M

1 (b)
Solve following recurrence:

t(n)-2 t(n-1)=3

t(n)-2 t(n-1)=3

^{n}.
8 M

2 (a)
Write an algorithm for Knapsack greedy problem. Find an optimal solution for following knapsack problem: n=4, M=70, w= {10, 20, 30, 40}, P = {20, 30, 40, 50}

10 M

2 (b)
Write an algorithm for merge sort. State its time complexity by solving recurrence equation of merge sort.

8 M

Answer any one question from Q3 and Q4

3 (a)
Let n = 4 and {k1, k2, k3, k4} = {do, if, int, while}.

Let p(1:4) = {3, 3, 1, 1}

Let q(0:4) = {2, 3, 1, 1, 1}

Compute & construct OBST for above values.

Let p(1:4) = {3, 3, 1, 1}

Let q(0:4) = {2, 3, 1, 1, 1}

Compute & construct OBST for above values.

8 M

3 (b)
State and explain the principle of dynamic programming. Name the elements of dynamic programming and give the difference between dynamic programming and Greedy method.

8 M

4 (a)
Explain multistage graph problem with forward approach 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 | 10 | 15 | 20 |

5 | 0 | 9 | 10 |

6 | 13 | 0 | 12 |

8 | 8 | 9 | 0 |

8 M

Answer any one question from Q5 and Q6

5 (a)
Explain in detail backtracking strategy and give control abstraction for the same.

8 M

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

8 M

6 (a)
Write an algorithm on Hamiltonian cycles using Backtracking Strategy.

8 M

6 (b)
Write an 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)
State and explain in detail Cook's theorem.

10 M

7 (b)
Describe with example following class:

i) P ii) NP

i) P ii) NP

8 M

8 (a)
Prove that CNF-SAT is polynomially transformable to DHC, hence DHC is NP-complete.

10 M

8 (b)
Explain NP hard code generation problem.

8 M

Answer any one question from Q9 and Q10

9 (a)
Explain in detail with example Logarithmic time merging algorithm.

8 M

9 (b)
Explain with example parallel evaluation of expression.

8 M

10 (a)
Explain All pairs shortest paths. Also give parallel shortest paths algorithm.

8 M

10 (b)
State and explain pointer doubling problem with algorithm, what is the time complexity of this algorithm.

8 M

Answer any one question from Q11 and Q12

11 (a)
Explain Resource - Allocation algorithm with deadlock avoidance.

8 M

11 (b)
Explain in detail sorting and convex Hull algorithm.

8 M

12 (a)
Explain Image edge detection algorithm.

8 M

12 (b)
Explain how Huffman's technique is used for data coding.

8 M

More question papers from Design & Analysis of Algorithms