15

16

17

18

19

a)

b)
०)

8)

०)

8)
0)
6)
a)
b)

03000CS302052102

PART E

Answer any four full questions, each carries 10 marks.
Apply these algorithms on the following graph. Let A be the source vertex.

Analyse complexity of each algorithm.

i) നട ii) Kruskal

Give a comparison between dynamic programming and divide and conquer
strategy.

Explain greedy approach. Write general Greedy Algorithm.

Explain the differences between Prim’s and Kruskal’s Minimum Spanning Tree
algorithms.

Formulate fractional Knapsack problem. Write greedy algorithm for fractional
Knapsack problem.

Find optimal solution for the following Knapsack problem.

n=3, m=20, W={ 18,15,10 } , P={25,24, 20 }

Define N-Queens problem. Write down and explain an algorithm to solve N-
Queens problem using Backtracking technique. Illustrate it with suitable
example.

Define NP-Hard and NP-complete problems.

What do you mean by intractable problems?

Write notes on polynomial time reducibility. Give examples.

Define Travelling Salesman Problem (TSP).

Explain the basic steps that are to be followed to solve TSP using branch and

bound. Illustrate with an example.

नैनः नैनः

Page 3 of 3

(10)

(3)

(5)
(2)

(4)

(6)

(10)

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