17

18

19

20

b)

b)

a)

b)

A6810 Pages: 4
implying that P= NP?
Prove that CLIQUE problem is NP-complete.
Explain the concept of Backtracking. Explain how 4 Queen problem can be (10)
solved using backtracking. Draw the state space tree corresponding to 4 Queen
problem.
Define Travelling Salesman Problem (TSP). Explain the basic steps that are 10 (10)
be followed to solve TSP using branch and bound. Illustrate with an example.
State fractional knapsack problem. Give an algorithm for fractional knapsack (5)
problem using greedy strategy.
Find an optimal solution to the fractional knapsack problem for an instance (4)
with number of items 7, Capacity of the sack W=15, profit associated with the
items (pl,p2,...,.p7)= (10,5,15,7,6,18,3) and weight associated with each
item (wW1,w2,...,w7} (2,3,5,7,1,4,1).

Find the number of distinct minimum spanning trees for the weighted graph (4)
below

Consider a weighted complete graph G on the vertex set {vl,v2,...,.vn} such (3)
that the weight of the edge (vi,vj) is 21-1( Find the weight of a minimum
spanning tree of ൨.

Specify the difference between divide and conquer strategy and dynamic (3)

programming.

با ید كد یھ

Page 4 of 4