written 6.8 years ago by |
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 |
(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)