Download JNTU Kakinada B.Tech 1-1 2013 Nov R10 MATHEMATICS I Question Paper

ANURAG GROUP OF INSTITUTIONS

(Autonomous)

III Year B.Tech I Semester Regular Examinations Nov/Dec 2023

DESIGN AND ANALYSIS OF ALGORITHMS

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

(Computer Science and Engineering)

Time: 3 Hours Max. Marks: 70

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

PART - A (10 x 2 = 20 Marks)

1. Define Algorithm. Explain the characteristics of an algorithm.
2. What are the various asymptotic notations used in algorithm analysis?

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

3. Write an algorithm for Binary Search.
4. What is the use of divide and conquer strategy?
5. Define Minimum Spanning Tree.
6. What is the basic principle of the greedy approach?
7. Define the single source shortest path problem.

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

8. What is dynamic programming? List out the properties of dynamic programming.
9. Define Graph Coloring.
10. What is the use of Backtracking?

PART - B (5 x 10 = 50 Marks)

Note: Answer any five questions.

1. a) Explain about asymptotic notations with examples. (5M)

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

   b) Explain Linear and Non-Linear data structures. (5M)

2. Explain Merge Sort algorithm with an example and derive its time complexity. (10M)

3. Explain Prim’s algorithm with an example. (10M)

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

4. Explain the Dijkstra’s algorithm with an example. (10M)

5. What is 0/1 knapsack problem? Solve the following instance of the 0/1 knapsack problem using dynamic programming. (10M)

   n = 3, capacity = 5

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

   Items: {(1, 6), (2, 10), (3, 12)}

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

7. What is n-Queen’s problem? Explain the algorithm to solve the n-Queen’s problem. (10M)

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

8. Write short notes on the following: (10M)

   a) NP-Hard (5M)

   b) NP-Complete (5M)

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

Visit FirstRanker.com for more question papers.