CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS PART B QUESTIONS

PART-B

I-UNIT

1. (a) Describe the steps in analyzing & coding an algorithm. (10)

    (b) Explain some of the problem types used in the design of

          algorithm. (6)

2.(a) Discuss the fundamentals of analysis framework . (10)

   (b) Explain the various asymptotic notations used in algorithm design. (6)

3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)

    (b) Explain the various Asymptotic efficiencies of an algorithm. (8)

4. (a) Explain the basic efficiency classes. (10)

    (b) Explain briefly the concept of algorithmic strategies. (6)

5. Describe briefly the notions of complexity of an algorithm. (16)

6. (a) What is Pseudo-code?Explain with an example. (8)

    (b) Find the complexity C(n) of the algorithm for the worst

     case,best case and average case.(Evaluate average case complexity for n=3,Where n is the   

     number of inputs) (8)

7. Set up & solve a recurrence relation for the number of key comparisons made by above  

     pseudo code. (4)

II-UNIT

1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)

2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)

3) Explain about Knapsack Problem with example

4) Explain Dijikstra algorithm (8)

5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning   

    tree with an example. (16)

6)Explain Kruskal’s algorithm. (8)

7) Explain about binary search with example.

III-UNIT

1) Solve the all pair shortest path problem for the diagraph with the weighted matrix given below:-

a b c d

a 0 ∞ 3 ∞

b 2 0 ∞ ∞

c ∞ 7 0 1

d 6 ∞ ∞ 0(16)

2) Explain Warshall’s & Floyd’s Algorithm. (16)

3) Explain about Multistage graphs with example.

4) Define optimal binary search trees with example.

5) Explain 0/1 knapsack problem with example.

6) Discuss the solution for Travelling salesman problem using branch & bound technique. (16)

VI-UNIT

1. Explain the 8-Queen’s problem & discuss the possible solutions. (16)

2. Solve the following instance of the knapsack problem by the branch & bound algorithm. (16)

3. Apply backtracking technique to solve the following instance of subset sum problem :    

    S={1,3,4,5} and d=11 (16)

5. Explain subset sum problem & discuss the possible solution strategies using backtracking.(16)

6. Explain Graph coloring with example.

7. Explain about Knapsack Problem using back tracking with example.

                                                                        V-UNIT

1. Give a suitable example & explain the Breadth first search & Depth first search. (16)

2. Explain about biconnected components with example.

3. Briefly explain NP-Hard and NP-Completeness with examples.

4. Explain about 0/1 Knapsack Problem using branch and bound with example.