Design and Analysis of Algorithms - May 2015

Information Technology Engineering (Semester 6)

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 following recurrence relation:
T(n)=T(n/2)+1
T(1)=1(5 marks) 1 (b) Analyze merge sort and find time complexity of merge sort.(5 marks) 10 (a) Specify one example of NP-hard problem. Also mention that why it is NP hard.(8 marks) 10 (b) Explain in detail models for parallel computing.(8 marks) 2 (a) Write an algorithm to find factorial using recursion. Find the time complexity.(5 marks) 2 (b) Consider following instance for simple knapsack problem. Find the solution using greedy method.
N=8
P = {11, 21, 31, 33, 43, 53, 55, 65}
W = {1, 11, 21, 23, 33, 43, 45, 55}
M =110(5 marks)

Answer any one question from Q3 and Q4

3 (a) Write Krushal's algorithm to find minimum spanning tree.(5 marks) 3 (b) Write Floyd's algorithm for all pairs shortest path and find time complexity.(5 marks) 4 (a) Solve the following job sequencing problem using greedy algorithm.
N(Number of jobs)=4
Profits associated with jobs (P₁, P₂, P₃, P₄) = (100, 10, 15, 27). Deadline associated with jobs (d₁, d₂, d₃, d₄) = (2, 1, 2, 1).(5 marks) 4 (b) What is principle of optimality? Differentiate between greedy and dynamic method.(5 marks)

Answer any one question from Q5 and Q6

5 (a) Writ recursive backtracking algorithm for sum of subnet problem.(8 marks) 5 (b) Write an algorithm for 0/1 knapsack problem using backtracking method.(8 marks) 6 (a) What is backtracking? Write general iterative algorithm for backtracking.(8 marks) 6 (b) Write short note on:
i) State space tree
ii) Live node
iii) Expanding node (E-node)
iv) Bounding function(8 marks)

Answer any one question from Q7 and Q8

7 (a) Explain the term:
i) Least cost branch and bound.
ii) Compare backtracking and branch and bound method.(10 marks) 7 (b) Consider 0/1 Knapsack instance n=4 with capacity 10 kg. such that

Answer any one question from Q9 and Q10

9 (a) Prove that Clique problem is NP complete.(8 marks) 9 (b) Explain how parallel computations are possible using complete binary tree.(8 marks)