## Design & Analysis of Algorithms - May 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)** Write the recurrence relation for binary search and solve it.(6 marks)
**1 (b)** Explain the Greedy Prim's minimum spanning tree algorithm.(4 marks)
**1 (c)** Write control abstraction for divide and conquer algorithmic strategy. Also write recurrence relation for the same.(5 marks)
**1 (d)** Define asymptotic notations. Explain their significance in analyzing algorithms.(3 marks)
**10 (a)** Explain how graph problems can be solved using parallel processors.(8 marks)
**10 (b)** Explain in detail parallel MERGE sorting.(8 marks)

### Answer any one question from Q11 and Q12

**11 (a)** Explain Deadlock detection and avoidance algorithm.(8 marks)
**11 (b)** What is meant by heuristic algorithms? Discuss any one heuristic search algorithm.(8 marks)
**12 (a)** Explain convex hull algorithm. Comment on the time complexity.(8 marks)
**12 (b)** Explain resource allocation algorithm for deadlock avoidance.(8 marks)
**2 (a)** Write an algorithm for quick sort. State its time complexity.(6 marks)
**2 (b)** Solve the following instance of 'job sequencing with deadlines' problem: n = 7, profits (p1, p2, p3, ........,p7) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d1, d2, ........., d7) = (1, 3, 4, 3, 2, 1, 2)(4 marks)
**2 (c)** Obtain a set of optimal Huffman codes for the messages (M1, M2, ..... M6) with relative frequencies (q1, q2, ....... q6) = (2, 3, 5, 7, 9, 13). Draw the decode tree for this set of codes.(8 marks)

### Answer any one question from Q3 and Q4

**3 (a)** Let n = 3 and {k1, k2, k3} = {do, if, while} Let p (1:3) = {0.5, 0.1, 0.05} Let q (0:3} = {0.15, 0.1, 0.05, 0.05} Compute & construct OBST for above values.(9 marks)
**3 (b)** State multistage graph problem and explain how it can be solved using forward approach.(7 marks)
**4 (a)** Explain 0/1 Knapsack using dynamic programming with an example.(8 marks)
**4 (b)** Define the Travelling Salesperson Problem. Solve the TSP problem using Dynamic programming where the edge lengths are given as:

0 | 9 | 8 | 8 |

12 | 0 | 13 | 6 |

10 | 9 | 0 | 5 |

20 | 15 | 10 | 0 |

### Answer any one question from Q5 and Q6

**5 (a)** What are implicit and explicit constraints with respect to backtracking?(8 marks)
**5 (b)** Write the control abstraction for LC-Search. Explain how Travelling Salesperson problem is solved using LCBB.(8 marks)
**6 (a)** Write recursive algorithm on Graph Colouring using Backtracking Strategy. Determine the time complexity of the same.(8 marks)
**6 (b)** Write an iterative algorithm to solve n Queen's problem using backtracking methods. What is the time complexity of this algorithm?(8 marks)

### Answer any one question from Q7 and Q8

**7 (a)** Prove that vertex cover problem is NP complete.(9 marks)
**7 (b)** Show that the sum of subsets problem is NP-Hard, given that Exact cover problem is NP-Hard.(9 marks)
**8 (a)** What is meant by a problem 'reducing to' another problem? Prove that the clique decision problem reduces to node cover decision problem.(8 marks)
**8 (b)** Explain NP-Hard scheduling problem with example. Also comment on the time complexity.(10 marks)

### Answer any one question from Q9 and Q10

**9 (a)** Write an algorithm for Odd-Even merge. Determine its time complexity.(8 marks)
**9 (b)** Consider the following expression:

((7 - (21 / 3)) * 3) + ((9 * (10 - 8)) + 6) Explain how it can be evaluated parallel.(8 marks)