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:

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)