JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

R18 B.Tech. II Year II Sem Examinations, November/December - 2020

DESIGN AND ANALYSIS OF ALGORITHMS

(Common to CSE, IT)

Time: 2 Hours Max. Marks: 75

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

Answer any five questions

All questions carry equal marks

1. a) Explain the various criteria used to analyze algorithms. [7M]
   b) Write an algorithm for finding the transpose of a given matrix and also determine the time complexity of the algorithm. [8M]
2. a) Explain the features of divide and conquer algorithm. [7M]
   

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

   b) Write a recursive algorithm for finding the maximum and minimum elements in an array. [8M]
3. Write an algorithm for finding a minimum spanning tree using Prim’s algorithm. Explain with an example. [15M]
4. a) Write the control abstraction for Divide and Conquer. [7M]
   b) Explain the greedy algorithm to solve Knapsack problem with example. [8M]
5. a) Define single source shortest path problem. [7M]
   

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

   b) Describe an algorithm to find the shortest path from a single source to all other vertices in a digraph with positive edge weights. [8M]
6. a) How to solve the All Pairs Shortest Path Problem using Dynamic Programming approach. Explain. [7M]
   b) Write short notes on Travelling Sales Person problem. [8M]
7. a) Explain graph coloring problem. [7M]
   b) Explain the sum of subsets problem with an example. [8M]

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

8. a) Explain the vertex cover problem. [7M]
   b) What is a Hamiltonian cycle? Explain how to find Hamiltonian cycles using backtracking. [8M]

---ooOoo---

Get more previous year question papers at FirstRanker.com

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