STUPIDSID
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