SPPU Information Technology (Semester 6)
Design and Analysis of Algorithms
May 2017
Total marks: --
Total time: --
(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:
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.
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