This download link is referred from the post: AKTU B-Tech Last 10 Years 2010-2020 Previous Question Papers || Dr. A.P.J. Abdul Kalam Technical University
ANURAG GROUP OF INSTITUTIONS
(Autonomous)
B.Tech III Year II Semester Regular Examinations, April/May - 2023
DESIGN AND ANALYSIS OF ALGORITHMS
(Computer Science and Engineering)
--- Content provided by FirstRanker.com ---
Time: 3 Hours Max. Marks: 70
Note: Answer all questions from Part A and Part B. Each question carries equal marks.
PART – A (10 × 2 = 20 Marks)
- Define Algorithm. Explain the properties of an algorithm.
- What is amortized analysis? Explain briefly.
- Write the advantages of Divide and Conquer technique.
- Define optimal binary search tree.
- What is a Minimum Cost Spanning Tree?
- Write an algorithm to find single source shortest path.
- Define Back Tracking.
- Differentiate between Branch and Bound and Backtracking.
- Define NP-Hard and NP-Complete problems.
- State cook’s theorem.
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
PART – B (5 × 10 = 50 Marks)
Note: Answer all questions. Each question carries equal marks.
- a) Explain Asymptotic Notations with examples. (5M)
OR--- Content provided by FirstRanker.com ---
b) Explain in detail about probabilistic analysis. (5M) - a) Explain Merge sort with an example and analyze its time complexity. (5M)
OR
b) Find an 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) - a) Explain Prim’s algorithm to find the minimum cost spanning tree with an example. (5M)
--- Content provided by FirstRanker.com ---
OR
b) Explain Single Source Shortest Path algorithm with an example. (5M) - a) Explain Graph Coloring using Backtracking. (5M)
OR
b) What is Hamiltonian cycle? Explain how to find Hamiltonian cycle using backtracking. (5M) - a) Explain the Classes P and NP. (5M)
OR
b) Explain the vertex cover problem with suitable example. (5M)
--- Content provided by FirstRanker.com ---
--- Content provided by FirstRanker.com ---
This download link is referred from the post: AKTU B-Tech Last 10 Years 2010-2020 Previous Question Papers || Dr. A.P.J. Abdul Kalam Technical University