JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

R18 B.Tech. III Year I Semester Examinations, January - 2022

DESIGN AND ANALYSIS OF ALGORITHMS

(Computer Science and Engineering)

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

Time: 3 Hours Max. Marks: 75

Note: This question paper contains two parts A and B.

Part A is compulsory which carries 25 marks. Answer all questions in Part A.

Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks.

PART – A (25 Marks)

1. 1. What are the characteristics of an algorithm? (2M)

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

   2. Define space complexity? (3M)
   3. Write the applications of Greedy method. (2M)
   4. Define minimum cost spanning tree. (3M)
   5. Write about principle of optimality. (2M)
   6. What is the use of dynamic programming? (3M)

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

   7. Define articulation point. (2M)
   8. Explain about graph coloring. (3M)
   9. Define NP-complete problem. (2M)
   10. Briefly explain about clique decision problem. (3M)

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

PART – B (50 Marks)

(Answer any one full question from each unit)

UNIT - I

1. a) Explain the Asymptotic notations with examples. (5M)
   b) Write an algorithm for finding the maximum and minimum elements in an array. (5M)

   OR

2. a) Explain the general plan for analyzing the efficiency of nonrecursive algorithms. (5M)
   

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

   b) Solve the following recurrence equation T(n)= 4T(n/2) + n, using Master's Theorem. (5M)

UNIT - II

1. a) Write the algorithm for single source shortest path problem. (5M)
   b) Explain Prim’s algorithm with an example. (5M)

   OR

2. Explain Dijikstra's algorithm with example. (10M)

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

UNIT - III

1. a) Explain the general method of Dynamic programming. (5M)
   b) Find the 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)

   OR

2. Explain the travelling salesperson problem with example. (10M)

UNIT - IV

1. a) Explain Breadth First Search traversal with an example. (5M)
   

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

   b) Explain Depth First Search traversal with an example. (5M)

   OR

2. Explain Bi-connected components with an example. (10M)

UNIT - V

1. Explain the classes of NP-Hard and NP-Complete. (10M)

   OR

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

2. Write non-deterministic algorithm for sorting. (10M)

---ooOoo---

Get more study materials at FirstRanker.com