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² - 6n=θ (n²).(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₁, W₂, 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)