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
What is Amortized complexity ?
Answer
Amortized complexity is the average time taken per operation over a worst-case sequence of operations. It ensures that while a single operation might be expensive, the total time for a sequence of operations is bounded, providing a more accurate measure of performance than worst-case analysis of a single operation.
Write down the importance of Space complexity.
Answer
Space complexity is essential because it measures the amount of memory an algorithm requires as a function of the input size. It is critical for determining if an algorithm can execute within the available hardware memory limits, preventing stack overflow or out-of-memory errors, and is often a trade-off factor against time complexity.
Define spanning tree.
Answer
Sign in to view the complete answer paper.
Mention the types of Binary tree traversal.
Answer
Sign in to view the complete answer paper.
Define Job sequencing with deadlines.
Answer
Sign in to view the complete answer paper.
What do you mean by Multistage Graphs?
Answer
Sign in to view the complete answer paper.
What is Hamiltonian Cycles?
Answer
Sign in to view the complete answer paper.
Specify the uses of Graph coloring techniques.
Answer
Sign in to view the complete answer paper.
Define NP hard problem.
Answer
Sign in to view the complete answer paper.
Write about Node cover decision problem.
Answer
Sign in to view the complete answer paper.
Part B
Define sorting.
Answer
Sign in to view the complete answer paper.
Illustrate on Strassen’s Matrix Multiplication.
Answer
Sign in to view the complete answer paper.
Specify how the merge sort takes place?
Answer
Sign in to view the complete answer paper.
Enumerate on Asymptotic Notations in detail.
Answer
Sign in to view the complete answer paper.
Explain about Probabilistic analysis of an algorithm.
Answer
Sign in to view the complete answer paper.
Explain the working principles of divide and conquer method.
Answer
Sign in to view the complete answer paper.
Explain about the union and find algorithms in detail.
Answer
Sign in to view the complete answer paper.
Give the algorithm of Breadth first search tree traversal.
Answer
Sign in to view the complete answer paper.
List out the differences between connected components and Bi connected components.
Answer
Sign in to view the complete answer paper.
Explain about AND/OR graphs in detail.
Answer
Sign in to view the complete answer paper.
Define tree.
Answer
Sign in to view the complete answer paper.
What do you mean by game trees? Explain.
Answer
Sign in to view the complete answer paper.
Define Graph.
Answer
Sign in to view the complete answer paper.
Brief about Single source shortest path.
Answer
Sign in to view the complete answer paper.
Enumerate on optimal binary search trees.
Answer
Sign in to view the complete answer paper.
What do you mean by Reliability design?
Answer
Sign in to view the complete answer paper.
Explain in detail about all pair shortest problem.
Answer
Sign in to view the complete answer paper.
Give an algorithm of 0/1 Knapsack problem of dynamic programming.
Answer
Sign in to view the complete answer paper.
Explain the General Backtracking method in detail.
Answer
Sign in to view the complete answer paper.
State and prove sum of subsets problem.
Answer
Sign in to view the complete answer paper.
Explain about Graph coloring in detail.
Answer
Sign in to view the complete answer paper.
Illustrate on FIFO Branch and Bound solution.
Answer
Sign in to view the complete answer paper.
Define Recursive method.
Answer
Sign in to view the complete answer paper.
Define Non deterministic algorithm.
Answer
Sign in to view the complete answer paper.
Write down the nondeterministic clique pseudocode.
Answer
Sign in to view the complete answer paper.
Give six sub formulas for assertions in cook’s theorem.
Answer
Sign in to view the complete answer paper.
Write down the nondeterministic search algorithm.
Answer
Sign in to view the complete answer paper.
How the nondeterministic algorithm supports Maximum clique? Explain.
Answer
Sign in to view the complete answer paper.
How to attain satisfiability in Nondeterministic algorithms?
Answer
Sign in to view the complete answer paper.