ANURAG GROUP OF INSTITUTIONS

(Autonomous)

B.Tech III Year I Semester Examinations, November/December - 2023

DESIGN AND ANALYSIS OF ALGORITHMS

Time: 3 Hours Max. Marks: 70

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

Note: Answer all questions from Part A and Part B.

PART - A (10 x 2 = 20 Marks)

1. Define Algorithm.
2. Write the properties of Big-O notation.
3. Define Divide and Conquer Technique.
4. Differentiate Greedy method and Dynamic programming.

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

5. What is Minimum Cost Spanning Tree?
6. Write any two differences between DFS and BFS.
7. Define Back Tracking.
8. What is Hamiltonian Cycle?
9. Define NP-Hard and NP-Complete problems.

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

10. List any four NP-Complete problems.

PART - B (5 x 10 = 50 Marks)

11. a) Explain the Asymptotic Notations with examples.

OR

b) i. Explain the Multistage graphs with example.

ii. Write the algorithm for finding maximum and minimum using divide and conquer technique.

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

12. a) Discuss the greedy algorithm for Knapsack problem.

OR

b) Explain Single Source Shortest Path Problem with example.

13. a) What is Minimum Cost Spanning Tree? Explain Prim’s Algorithm with example.

OR

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

b) Explain the Depth First Search Traversal with example.

14. a) Explain the 4-Queen Problem with example.

OR

b) Discuss the Sum of Subsets problem with example.

15. a) Explain the Non-Deterministic algorithms.

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

OR

b) Explain the Graph Coloring problem.

Visit FirstRanker.com for more question papers.