Question Paper: Design and Analysis of Algorithms : Question Paper May 2015 - Information Technology Engineering (Semester 6) | Pune University (PU)
0

## 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 (P1, P2, P3, P4) = (100, 10, 15, 27). Deadline associated with jobs (d1, d2, d3, d4) = (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

 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 =

 ∞ 20 30 10 11 15 ∞ 16 4 2 3 5 ∞ 2 4 19 6 18 ∞ 3 16 4 7 16 ∞

(18 marks)

### 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)

 written 3.0 years ago by Team Ques10 ♦♦ 400