B.E.
6th SEMENSTER (CSE)
Examination - May, 2012
ANALYSIS
AND DESIGN OF ALGORITHMS
Paper : CSE-306-F
Note :
Question No. 1 is compulsory. Attempt any five questions, selecting at least one
question from each part.
1. (a) A symptotic notations. 3
(b) Difference in Greedy and Dynamic approaches. 3
(c) NP Hard and NP complete problems. 4
(d) General backtracking method. 3
(e) Hamiltonian Cycles with examples. 4
(f) Recursive Relations. 3
Section-A
2. (a) Explain the following : Union and
fund operations in terms of set and Disjoint set. 10
(b) Which sorting algorithm is most efficient ? Explain various pros and
cons. 10
3. (a)Explain quick sort algorithm. 10
(b) Explain strassen’s matrix multiplication. 10
Section-B
4. (a) Generate the minimum spanning
tree of the following connected graph using Kruskal’s algorithm. 10
(b) Explain single source shortest path problem along with the algorithm,
example and its complexity.
1. Explain the problem of solving
optional binary search trees using dynamic programming. 20
Section –C
2. Suggest the solution to the following
problem using backtracking :
(a) 8-queen problem
(b) Graph – Coloring. 20
3. (a) Differentiate between
backtracking and branch and bound. 10
(b)Explain LC branch and bound with
example. 10
Section – D
4. (a) show that Clique decision problem
is NP Hard. 10
(b) Discuss Node cover
decision problem. 10
5. State and prove cook’s theorem. 20
No comments:
Post a Comment