JNTU
JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (August - 2022 - R18)
Answer any five questions
All questions carry equal marks
Main
Show that the following equalities are correct:
5n2 - 6n = θ(n2)
Answer
To show 5n2 - 6n = θ(n2), we must find constants c1, c2, and n0 such that c1n2 ≤ 5n2 - 6n ≤ c2n2 for all n ≥ n0. Dividing by n2, we need c1 ≤ 5 - 6/n ≤ c2. For n ≥ 2, 5 - 6/n ≥ 5 - 3 = 2, so c1 = 2. For all n ≥ 1, 5 - 6/n ≤ 5, so c2 = 5. Since constants exist for n ≥ 2, the equality holds.
n! = O(nn)
Answer
To show n! = O(nn), we must find c and n0 such that n! ≤ c(nn) for all n ≥ n0. We know that n! = 1 × 2 × 3 × ... × n. Since each term in the product 1, 2, ..., n is less than or equal to n, it follows that n! ≤ n × n × n × ... × n = nn. Thus, for c = 1 and n0 = 1, the condition n! ≤ 1(nn) is satisfied.
2n + n log n = θ(2n)
Answer
Sign in to view the complete answer paper.
n3 + 106n2 = θ(n3)
Answer
Sign in to view the complete answer paper.
What are asymptotic notations? Explain with examples.
Answer
Sign in to view the complete answer paper.
Write and explain quick sort algorithm with an example.
Answer
Sign in to view the complete answer paper.
Write and explain find algorithm with collapsing rule.
Answer
Sign in to view the complete answer paper.
Describe the general method of backtracking.
Answer
Sign in to view the complete answer paper.
What are union and find operations? Explain with suitable examples.
Answer
Sign in to view the complete answer paper.
Explain about graph coloring algorithm.
Answer
Sign in to view the complete answer paper.
Solve the following 0/1 knapsack problem using dynamic programming: n=3, (W1, W2, W3) = (2, 3, 3), (P1, P2, P3) = (1, 2, 4) and m=6.
Answer
Sign in to view the complete answer paper.
Differentiate between dynamic programming and divide and conquer.
Answer
Sign in to view the complete answer paper.
Consider four elements a1 < a2 < a3 < a4 with q(0,1,2,3,4) = (1/8, 3/16, 1/16, 1/16) and (p1, p2, p3, p4) = (1/4, 1/8, 1/16, 1/16). Construct the table of values of W(i, j), R(i, j) and C(i, j) computed by the algorithm to compute the roots of optimal sub-tree.
Answer
Sign in to view the complete answer paper.
Describe Greedy method control abstraction for the subset paradigm.
Answer
Sign in to view the complete answer paper.
Write an algorithm of Greedy knapsack.
Answer
Sign in to view the complete answer paper.
Write a non-deterministic algorithm of sorting a list of elements in an array.
Answer
Sign in to view the complete answer paper.
Explain the applications of branch and bound.
Answer
Sign in to view the complete answer paper.