## Design & Analysis of Algorithms - June 2015

### SPPU Computer Engineering (Semester 7)

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

### 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 marks

**1 (b)** Solve following recurrence:

t(n)-2 t(n-1)=3^{n}.
10 marks

**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 marks

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

### 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. 10 marks

**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.
10 marks

**4 (a)** Explain multistage graph problem with forward approach using dynamic programming with an example.
10 marks

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

### Answer any one question from Q5 and Q6

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

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

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

**6 (b)** Write an algorithm to solve n Queen's problem using backtracking methods. What is the time complexity of this algorithm?
10 marks

### Answer any one question from Q7 and Q8

**7 (a)**State and explain in detail Cook's theorem. 10 marks

**7 (b)** Describe with example following class:

i) P ii) NP
10 marks

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

**8 (b)** Explain NP hard code generation problem.
10 marks

### Answer any one question from Q9 and Q10

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

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

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

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

### Answer any one question from Q11 and Q12

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

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

**12 (a)** Explain Image edge detection algorithm.
10 marks

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