JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (April - 2018 - R13)
Note: This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks and may have a, b, c as sub questions.
Part A
Write the algorithm for recursive permutation generator.
Answer
To generate permutations of a list A[k...n]:
Algorithm Permute(A, k, n)
if k == n then
print A
else
for i = k to n do
swap(A[k], A[i])
Permute(A, k + 1, n)
swap(A[k], A[i])Explain the usefulness of the UNION operation on sets.
Answer
The UNION operation is fundamental in Disjoint Set Union (DSU) data structures. It is used to merge two disjoint sets into a single set. Its primary usefulness lies in efficiently tracking connected components in graphs (e.g., Kruskal's algorithm for Minimum Spanning Trees) and managing equivalence relations, where it helps determine if two elements belong to the same partition.
Write the control abstraction for greedy method.
Answer
Sign in to view the complete answer paper.
Discuss Knapsack problem.
Answer
Sign in to view the complete answer paper.
List out the advantages of dynamic programming.
Answer
Sign in to view the complete answer paper.
State the principle of optimality.
Answer
Sign in to view the complete answer paper.
List the applications of Backtracking.
Answer
Sign in to view the complete answer paper.
Give the solution for the 8 queens problem.
Answer
Sign in to view the complete answer paper.
Define class P.
Answer
Sign in to view the complete answer paper.
What are non-deterministic algorithms?
Answer
Sign in to view the complete answer paper.
Part B
Develop the algorithm for Find using collapsing rule with an example.
Answer
Sign in to view the complete answer paper.
Draw the tree of calls of merge sort for the following set (35, 25, 15, 10, 45, 75, 85, 65, 55, 5, 20, 18).
Answer
Sign in to view the complete answer paper.
Explain about Amortized Analysis.
Answer
Sign in to view the complete answer paper.
Analyze the time complexity of quick sort for best, average and worst cases.
Answer
Sign in to view the complete answer paper.
Demonstrate the kruskal’s algorithm to find the minimum spanning tree by taking an illustrative graph.
Answer
Sign in to view the complete answer paper.
Consider the following instance of Knapsack problem N=3, M=20, (p1,p2,p3)=(25,24,15), (w1,w2,w3)=(18,15,10). Calculate Maximum profit, Minimum weight and Maximum profit per unit weight.
Answer
Sign in to view the complete answer paper.
Explain job sequencing with deadlines with a suitable example.
Answer
Sign in to view the complete answer paper.
Illustrate single source shortest path problem with a suitable example.
Answer
Sign in to view the complete answer paper.
Write an algorithm for 0/1 Knapsack Problem using Dynamic Programming.
Answer
Sign in to view the complete answer paper.
Use function OBST to compute w(i,j), r(i,j) and c(i,j), 0<=I<j<=4, for the identifier set (a1, a2, a3, a4)=(count, float, if, while) with p(1)=1/20, p(2)=1/5, p(3)=1/10,p(4)=1/20, q(0)=1/5, q(1)=1/10, q(2)=1/5, q(3)=1/20, and q(4)=1/20. Using the r(i,j)’s, construct the Optimal Binary Search Tree.
Answer
Sign in to view the complete answer paper.
Consider three stages of a system with r1=0.3, r2=0.5, r3=0.2 and c1=30, c2=20, c3=30. Where the total cost of the system is C=80 and u1=2, u2=3, u3=2 find the reliability design.
Answer
Sign in to view the complete answer paper.
Explain and write the algorithm for travelling salesman problem.
Answer
Sign in to view the complete answer paper.
Describe the backtracking technique to m-coloring graph. Explain with an example.
Answer
Sign in to view the complete answer paper.
Discuss the general method of Branch and Bound.
Answer
Sign in to view the complete answer paper.
Briefly explain sum of subsets problem using backtracking. Explain its applications.
Answer
Sign in to view the complete answer paper.
Solve 0/1 knapsack problem using Branch and Bound.
Answer
Sign in to view the complete answer paper.
Briefly explain Cooks-theorem.
Answer
Sign in to view the complete answer paper.
Explain the NP, NP-Hard and NP- complete classes with suitable examples.
Answer
Sign in to view the complete answer paper.
How are P and NP problems related? Give the relation between NP-hard and NP problems.
Answer
Sign in to view the complete answer paper.
Compare and contrast deterministic and nondeterministic algorithms.
Answer
Sign in to view the complete answer paper.