B.Tech II Year II Semester Examinations, May - 2023
DESIGN AND ANALYSIS OF ALGORITHMS
(Computer Science and Engineering)
Time: 3 hours Max. Marks: 70
Note: Answer any five questions. All questions carry equal marks.
-
a) What are the characteristics of an algorithm? Explain briefly the Asymptotic notations.
b) Write an algorithm for finding factorial of ‘N’ numbers and determine the time and space complexity.
--- Content provided by FirstRanker.com ---
-
a) Explain the working principle of merge sort algorithm.
b) Sort the following list of elements using merge sort: 23, 35, 12, 4, 67, 5, 9, 11, 80, 32.
-
a) What is a spanning tree? Explain Prim's algorithm to find the minimum spanning tree of a graph.
--- Content provided by FirstRanker.com ---
b) Find the minimum spanning tree for the following graph using Prim's algorithm.
-
a) Write an algorithm to find the shortest path using Dijkstra’s algorithm.
b) Explain the difference between Dynamic programming and Greedy method.
-
a) What is the 0/1 Knapsack problem? Write the algorithm for solving 0/1 Knapsack problem using dynamic programming.
b) Find an optimal solution to the knapsack instance n=7, m=15 (p1, p2, ...p7)=(10, 5, 15, 7, 6, 18, 3) and (w1, w2, ...w7) = (2, 3, 5, 7, 1, 4, 1)
-
a) Explain the sum of subset problem and write the algorithm for it using backtracking.
b) Let W = {5, 10, 12, 13, 15, 18} and m = 30. Find all possible subsets of ‘w’ that sum to ‘m’ using backtracking algorithm.
--- Content provided by FirstRanker.com ---
-
a) Describe the N-Queen’s problem and explain the algorithm to solve it using backtracking.
b) Solve 4-Queen problem using backtracking approach.
-
a) Explain NP-Hard and NP-Complete problems.
--- Content provided by FirstRanker.com ---
b) Write short notes on the following:
- i) Cook’s theorem
- ii) Traveling sales person problem
--- Content provided by FirstRanker.com ---
Visit FirstRanker.com for more question papers.
--- Content provided by FirstRanker.com ---