B.Tech II Year II Semester Examinations, May - 2019

DESIGN AND ANALYSIS OF ALGORITHMS

(Common to CSE, IT)

Time: 3 hours

Max. Marks: 75

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

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

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. Define Pseudo code. (2 Marks)
   2. Write the time complexity of merge sort and quick sort. (3 Marks)
   3. What is spanning tree? (2 Marks)

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

   4. Define principle of optimality. (3 Marks)
   5. What is Back Tracking? (2 Marks)
   6. Define Graph Coloring. (3 Marks)
   7. Write any two differences between Dynamic Programming and Greedy Method. (2 Marks)
   8. What is the use of Lower Bound Theory? (3 Marks)

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

   9. Define NP-Hard and NP-Complete problems. (2 Marks)
   10. What do you mean by state space tree? (3 Marks)

PART - B (50 Marks)

(Answer any one full question from each unit. Each question carries 10 marks)

UNIT - I

1. Explain different Asymptotic notations with examples.

   OR

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

   Explain Binary search algorithm with example.

UNIT - II

1. Write an algorithm for finding minimum spanning tree using prim’s algorithm.

   OR

   Find single source shortest path for the following graph using Dijkstra’s algorithm.

UNIT - III

1. Solve the following 0/1 Knapsack problem using dynamic programming. Number of items n=4, Capacity of knapsack m=5. Weights (w1, w2, w3, w4) = (2, 3, 4, 5) and Values (p1, p2, p3, p4) = (3, 7, 2, 9).

   OR

   Explain optimal binary search tree with example.

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

UNIT - IV

1. Explain Graph coloring with example.

   OR

   Explain Sum of subsets problem with example.

UNIT - V

1. Explain NP-Hard and NP-Complete problems with examples.

   OR

   Explain Clique Decision Problem.

---oo0oo---

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

Visit FirstRanker.com for more question papers.