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

Design and Analysis of Algorithms - Dec 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.


Solve 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) Explain : NP-Hard, NP-Complete, Decision Problem and Polynomial Time Algorithm.(8 marks) 10 (b) Write an algorithm for pointer doubling problem. What is the time complexity of this algorithm?(8 marks) 2 (a) Write an algorithm to solve 'Tower of Hanoi' problem.(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)


Solve any one question from Q3 and Q4

3 (a) Write Prim's algorithm to find minimum spanning tree.(5 marks) 3 (b) What is Principle of optimality? Differentiate between greedy and dynamic method.(5 marks) 4 (a) Write Dijkstra's algorithm to find all pairs shortest path.(5 marks) 4 (b) Write short note on: Proof by counterexample.(5 marks)


Solve any one question from Q5 and Q6

5 (a) Write an algorithm to find Hamiltonian path using backtracking method.(8 marks) 5 (b) Differentiate between backtracking and branch and bound. Draw state space tree for given sum of subset problem:
Set of elements = {3, 5, 6, 7} and d = 15
(8 marks)
6 (a) What is backtracking? Write general recursive algorithm for backtracking.(8 marks) 6 (b) Discuss and analyze problem of graph coloring using backtracking with the help of example.(8 marks)


Solve any one question from Q7 and Q8

7 (a) Describe in brief the general strategy used in branch and bound method. Write general algorithm for Branch and Bound Method.(10 marks) 7 (b) Consider 0/1 Knapsack instance n = 4 with capacity 10 kg. such that
Find maximum profit using Least Cost branch and bound (LCBB) method. Use fixed size formation for state space tree.

Item Profit (in Rs.) Weight (in Kg)
1 40 4
2 42 7
3 20 5
4 12 3
(8 marks) 8 What is travelling salesman problem? Find the solution of following travelling salesman problem using branch and bound method.

(18 marks)


Solve any one question from Q9 and Q10

9 (a) Prove that vertex cover problem is NP complete.(8 marks) 9 (b) Explain in detail models for parallel computing.(8 marks)

Please log in to add an answer.