 MORE IN Design and Analysis of Algorithms
SPPU Information Technology (Semester 6)
Design and Analysis of Algorithms
May 2017
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

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