## Design & Analysis of Algorithms - Dec 2014

### Computer Engg (Semester 7)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.

### Answer any one question from Q1 and Q2

**1 (a)** Solve the recurrence relation

T (n) = T (n - 1) + T(n - 3) - T (n - 4), n> = 4 subject to T (n) = n for 0 < = n < = 3.(8 marks)
**1 (b)** Write an algorithm for insertion sort. State its time complexity.(6 marks)
**1 (c)** Explain with example the notations Big - O and Omega.(4 marks)
**10 (a)** State and explain different parallel computational models.(8 marks)
**10 (b)** Write an algorithm for odd-even merge sort & Illustrate it with following set of numbers. 2, 4, 3, 5, 6, 1, 7, 8.(8 marks)

### Answer any one question from Q11 and Q12

**11 (a)** Write an algorithm to implement Hoffman coding algorithm.(6 marks)
**11 (b)** What do you mean by Heuristic search algorithm? Explain it in brief with suitable example.(8 marks)
**11 (c)** State and explain Resource allocation algorithm(4 marks)
**12 (a)** State and explain Image edge detection algorithm.(8 marks)
**12 (b)** What is meaning of deadlock detection and deadlock avoidance ? What are the necessary conditions for deadlock to occur?(6 marks)
**12 (c)** Explain convex Hulls problem.(4 marks)
**2 (a)** Write Prim's algorithm for minimum spanning tree. Analyze the algorithm for time complexity.(8 marks)
**2 (b)** Explain Divide and conquer strategy with example of Binary Search(6 marks)
**2 (c)** Show that the following equality is correct 5n^{2} - 6n=θ (n^{2}).(4 marks)

### Answer any one question from Q3 and Q4

**3 (a)** Let n = 4 and (a1, a2, a3, a4) = (do, if, int, while), let p (1:4) = (3, 3, 1, 1) and q (0 : 4 ) = (2, 3, 1, 1), construct OBST using dynamic programming.(8 marks)
**3 (b)** What is dynamic programming? Define principle of optimality and explain it for 0/1 Knapsack.(8 marks)
**4 (a)** State multistage graphs problem and explain how it can be solved using backward approach.(8 marks)
**4 (b)** Find optimal solution for 0/1 Knapsack problem using Dynamic programming.

n=3, (W_{1}, W_{2}, W_{3)= (1,2,3) (P1, P2, P3)=(1,2,4) and m=6.}(8 marks)

### Answer any one question from Q5 and Q6

**5 (a)** Write an algorithm to solve 8-Queens problem using back tracking.(8 marks)
**5 (b)** Explain the steps of solving Travelling salesMan problem using Branch and Bound.(8 marks)
**6 (a)** Explain Graph colouring problem with respect to backtracking.(8 marks)
**6 (b)** What is Branch and Bound method? Explain FIFO Branch and Bound algorithm.(8 marks)

### Answer any one question from Q7 and Q8

**7 (a)** Write Cook's algorithm in pseudo C and find out its time complexity. State the significance of this algorithm.(8 marks)
**7 (b)** Consider scheduling problem where six jobs have a profit of (10, 34, 67, 45, 23, 99) and corresponding deadlines (2, 3, 1, 4, 5, 3). Obtain optimum schedule. What is time complexity of your algorithm?(8 marks)
**8 (a)** Reduce the following circuit satisfiability to formula a satisfiability.

(6 marks)
**8 (b)** Define a Clique problem. Find out all possible Cliques for following graph. Does it contains a Clique of maximum size?

(6 marks)

### Answer any one question from Q9 and Q10

**9 (a)** Explain pointer doubling algorithm with suitable example.(8 marks)
**9 (b)** How Quick sort can be implemented on multiprocessor system? Explain it with suitable Example.(8 marks)