ANURAG GROUP OF INSTITUTIONS

(Autonomous)

B.Tech III Year II Semester Regular Examinations, April/May - 2023

DESIGN AND ANALYSIS OF ALGORITHMS

(Computer Science and Engineering)

--- Content provided by‍ FirstRanker.com ---

Time: 3 Hours Max. Marks: 70

Note: Answer all questions from Part A and Part B. Each question carries equal marks.

PART – A (10 × 2 = 20 Marks)

1. Define Algorithm. Explain the properties of an algorithm.
2. What is amortized analysis? Explain briefly.
3. Write the advantages of Divide and Conquer technique.

--- Content provided by⁠ FirstRanker.com ---

4. Define optimal binary search tree.
5. What is a Minimum Cost Spanning Tree?
6. Write an algorithm to find single source shortest path.
7. Define Back Tracking.
8. Differentiate between Branch and Bound and Backtracking.

--- Content provided by‍ FirstRanker.com ---

9. Define NP-Hard and NP-Complete problems.
10. State cook’s theorem.

PART – B (5 × 10 = 50 Marks)

Note: Answer all questions. Each question carries equal marks.

1. a) Explain Asymptotic Notations with examples. (5M)
   OR
   

   --- Content provided by‍ FirstRanker.com ---

   b) Explain in detail about probabilistic analysis. (5M)
2. a) Explain Merge sort with an example and analyze its time complexity. (5M)
   OR
   b) Find an optimal solution to the knapsack instance n=7, m=15, (p1, p2,....p7) = (10, 5, 15, 7, 6, 18, 3), (w1, w2,....w7) = (2, 3, 5, 7, 1, 4, 1). (5M)
3. a) Explain Prim’s algorithm to find the minimum cost spanning tree with an example. (5M)
   

   --- Content provided by​ FirstRanker.com ---

   OR
   b) Explain Single Source Shortest Path algorithm with an example. (5M)
4. a) Explain Graph Coloring using Backtracking. (5M)
   OR
   b) What is Hamiltonian cycle? Explain how to find Hamiltonian cycle using backtracking. (5M)

--- Content provided by‌ FirstRanker.com ---

5. a) Explain the Classes P and NP. (5M)
   OR
   b) Explain the vertex cover problem with suitable example. (5M)

FirstRanker.com

--- Content provided by‍ FirstRanker.com ---