JNTU
JNTU B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (February - 2024 - R13)
Note: i) Question paper consists of Part A, Part B. ii) Part A is compulsory, which carries 25 marks. In Part A, answer all questions. iii) In Part B, Answer any one question from each unit. Each question carries 10 marks and may have a, b as sub questions.
PART - A
(25 Marks)
Define Omega notation.
Answer
The Omega notation (Ω-notation) provides an asymptotic lower bound on the growth rate of a function. For a given function g(n), Ω(g(n)) is defined as the set of functions f(n) such that there exist positive constants c and n₀ where 0 ≤ c · g(n) ≤ f(n) for all n ≥ n₀.
Write control abstraction algorithm of divide and conquer method.
Answer
The control abstraction for the divide and conquer method describes the general recursive structure used to solve a problem by breaking it into smaller subproblems. The algorithm is defined as follows:
if Small(P) then return S(P);
else {
divide P into smaller instances P1, P2, ..., Pk;
apply DAndC to each of these subproblems;
return Combine(DAndC(P1), DAndC(P2), ..., DAndC(Pk));
}
}
In this abstraction, Small(P) checks if the problem instance is small enough to be solved directly, S(P) provides the solution for the base case, and Combine merges the solutions of the subproblems to produce the final result for the original instance P.
Write an algorithm of Simple Union.
Answer
Sign in to view the complete answer paper.
Explain the properties of Biconnected components.
Answer
Sign in to view the complete answer paper.
State the Principle of optimality.
Answer
Sign in to view the complete answer paper.
Write the applications of Dynamic Programming.
Answer
Sign in to view the complete answer paper.
Explain the properties of LC Branch and Bound.
Answer
Sign in to view the complete answer paper.
Find the sum of subsets for the following set of integers by using fixed tuple method {5,10,15,20,18,12} for W = 30
Answer
Sign in to view the complete answer paper.
Write a non-deterministic algorithm to sort an elements in an array.
Answer
Sign in to view the complete answer paper.
What are the advantages of Non-deterministic algorithms?
Answer
Sign in to view the complete answer paper.
PART - B
(50 Marks)
Derive the time complexity of Strassen’s matrix multiplication.
Answer
Sign in to view the complete answer paper.
Explain about the Amortized analysis.
Answer
Sign in to view the complete answer paper.
Solve the following recurrence equation. T(n) = 4T(n/2) + n2, T(0) = 0
Answer
Sign in to view the complete answer paper.
Explain about the Binary Search with an example.
Answer
Sign in to view the complete answer paper.
Describe about the Biconnected Components with an example.
Answer
Sign in to view the complete answer paper.
Write an algorithm of DFS and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Write an algorithm of AND/OR graph.
Answer
Sign in to view the complete answer paper.
Explain the binary tree traversal with an example.
Answer
Sign in to view the complete answer paper.
Design a three stage system with device types D1, D2, D3. The costs all Rs. 30, Rs.15 and Rs 20 respectively. The cost of the system is to be no more than Rs.105. The reliability of each device type is 0.9, 0.8 and 0.5 respectively.
Answer
Sign in to view the complete answer paper.
Explain about the Job sequencing with deadlines.
Answer
Sign in to view the complete answer paper.
Write an algorithm of Greedy Knapsack problem and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Solve the TSP problem having the following cost-matrix using branch-and-bound technique.
| 0 | 10 | 15 | 20 |
| 5 | 0 | 9 | 10 |
| 6 | 13 | 0 | 12 |
| 8 | 8 | 9 | 0 |
Answer
Sign in to view the complete answer paper.
Write an algorithm of n-queens problem and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Explain about the sum of subsets problem with an example.
Answer
Sign in to view the complete answer paper.
Explain graph coloring problem is NP-Hard or NP- complete. Justify your answer.
Answer
Sign in to view the complete answer paper.
Write a non-deterministic algorithm of sum of subsets problem and also analyze the time complexity of the same
Answer
Sign in to view the complete answer paper.
Write a non-deterministic algorithm of 0/1 Knapsack problem and also analyze the time complexity of the same.
Answer
Sign in to view the complete answer paper.
Differentiate between Deterministic and non-deterministic algorithm.
Answer
Sign in to view the complete answer paper.