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 NPhard 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_{1}, P_{2}, P_{3}, P_{4}) = (100, 10, 15, 27). Deadline associated with jobs (d_{1}, d_{2}, d_{3}, d_{4}) = (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 (Enode)
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
Item  Profit (in Rs).  Weight (in kg) 
1  40  4 
2  42  7 
3  20  5 
4  12  5 
Find maximum profit using first in first out branch and bound (FIFOBB) method. Use fixed size formation for state space tree.(8 marks) 8 What is travelling salesman problem? Find the solution of following travelling salesman problem using branch and bound method.
Cost Matrix = 

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)