B.E. 5th SEMENSTER (CSE) Examination - December, 2010 ANALYSIS AND DESIGN OF ALGORITHMS

B.E. 5^th SEMENSTER (CSE)

Examination  - December, 2010

ANALYSIS AND DESIGN OF ALGORITHMS

Paper : CSE-305-E

Note  : Attempt any five questions. All questions carry equal marks.

1.      (a) What is bi-connected component of graph ? Give example of the bi-connected component. Write an algorithm to find the bi-connected components.                                                                                                             10

(b) Write algorithm for merge sort and find its complexity.                      10

2.     (a) Explain strassen’s matrix multiplication with suitable examples         10

(b)Explain the procedure of  quick sort with an example. Also analyse it in best ,average and worst cases.                                                                         10

3.     (a) What are minimum spanning trees? Give any one method to generate minimum spanning trees.                                                                   10

(b)Prove that the fractional knapsack problem has a greedy-choice property                                                                                                                       10

4.     (a) What is the principle of optimality that is used Dynamic programming paradigm? Discuss how this principle can be applied to shortest path problem.                                                                                                                    10

(b) Consider three items along with their respective weights and profits :

                        W_i  = (18, 15, 10)

                        P_i  = (25, 24, 15)

The knapsack has capacity, m=20, find out the solution to the fractional knapsack problem using Greedy Method.                                                      10

5.     (a) Write back- tracking procedure to determine all Hamiltonian cycle in a graph.                                                                                                               10

(b) Give an algorithm for graph colouring problem using Backtracking and analyze the time complexity of the same.                                       10

6.     Discuss all branch and bound strategies with the help of example.        20

7.     (a) Explain what do you mean by saying a problem  ₁ reduces to _2. How is it useful in proving problems NP-Complete ?                                             10

(b) Prove that Subset-sum Problem is in NP-Complete.                             10

8.     Write short notes on :

(a)  Union find algorithm

(b) Transitive closure of a graph

(c)  Optimal Binary Search tree