15

16

17

18

19

20

b)

a)
b)
a)
b)
a)
b)
a)
b)
௦)

a)
b)
௦)
a)
b)
०)

03000CS302052001

Is it possible to find all pairs of shortest paths using Dijkstra’s algorithm?
Justify.

PART E
Answer any four full questions, each carries10 marks.

Compare Divide and Conquer and Dynamic programming methodologies.
Write an algorithm to merge 2 sorted arrays into a single sorted array.
Explain Branch and bound technique.
How Travelling Salesperson Problem can be solved using Branch and bound.
Explain Kruskal’s algorithm with an example.
Derive its complexity of kruskal’salgorithm..
Explain control abstraction of greedy method.
Write greedy algorithm for knapsack problem.
Find an optimal solution to the knapsack instance 2-7
m=15,(pi,p2,.....p7)=(10,5,15,7,6,18,3) and (w1,Wg,.....W7)=(2,3,5,7,1,4,1).
Explain the concept of backtracking.
How backtracking can be used to solve N-queens problem.
Draw the state space tree for 4 Queens problem.
Define NP-Hard and NP-complete problems.
With examples explain polynomial time reducibility.

What do you mean by intractable problems?

Page 3 of 3

(2)

(4)
(6)
(3)
(7)
(6)
(4)
(3)
(4)
(3)

(3)
(4)
(3)
(4)
(4)
(2)