Solve any one question from Q.1(a,b) &Q.2(a,b)

1(a)
Prove by method of contradiction that " There is no greatest even integer"

5 M

1(b)
Write an Algorithm for binary serach and find the worst case efficiency.

5 M

2(a)
Set up a recurrence relation to compute n! And solve it.

5 M

2(b)
Consider the following letters with their probability.

Findout out Huffman coding for a, b, c, d, e.

Character | a | b | c | d | e |

Probability | 0.5 | 0.25 | 0.125 | 0.0625 | 0.031 |

Findout out Huffman coding for a, b, c, d, e.

5 M

Solve any one question from Q.3(a,b) &Q.4(a,b)

3(a)
Show the steps in multiplying the following two integers using efficiency integer multiplication method 2101×1130.

5 M

3(b)
Write Warshall's algorithm to find transitive closure.

5 M

4(a)
Solve the all pairs shortest path problem for the given graph:

!mage.

!mage.

5 M

4(b)
Explain the concept of divide and conquer technique. Write Master theorem.

5 M

Solve any one question from Q.5(a,b) &Q.6(a,b)

5(a)
Let W = {5, 10, 12, 13, 15, 18}, M = 30. Find all possible subsets of W that sum to M. Draw the portion of state space tree that is generated.

8 M

5(b)
Write a recursive backing algorithm for M-coloring of the graph.

8 M

6(a)
Construct planar graph for following map. Explain how to find M-colorings of this planar graph by using M-colorings backtracking algorithm.

!mage

!mage

8 M

6(b)
Write a recursive backtracking algorithm for sum of subset problem.

8 M

Solve any one question from Q.7 & Q.8(a,b)

7
What is travelling salesman problem? Find the solution of following travelling salesman problem using brach and bound method.

∞ | 20 | 30 | 10 | 11 |

15 | ∞ | 16 | 4 | 2 |

3 | 5 | ∞ | 2 | 4 |

19 | 6 | 18 | ∞ | 3 |

16 | 4 | 7 | 16 | ∞ |

18 M

8(a)
What is LC search? Explain in detail control abstraction for LC search.

8 M

8(b)
Solve the following instance of 0/1 knapsack problem by FIFO branch and bound approach: n = 4, M=15 and \[\left ( P_{1},P_{2},P_{3},P_{4} \right )=\left ( 10,10,12,18 \right );\left ( W_{1},W_{2} ,W_{3},W_{4}\right )=\left ( 2, 4, 6, 9 \right )\]

10 M

Solve any one question from Q.9(a,b) & Q.10(a,b)

9(a)
Specify one example of NP-complete problem. Also justify that why it is Np-complete.

8 M

9(b)
Explain pointer doubling algortihm.

8 M

10(a)
Explain the need and significance of parallel algorithms. Define the speedup of parallel algortihm.

8 M

10(b)
Prove that Vertex Cover problem is NP complete.

8 M

More question papers from Design and Analysis of Algorithms