JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B. Tech III Year DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (February - 2023 - R18)
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
What is an algorithm?
Answer
An algorithm is a finite, unambiguous, and step-by-step sequence of instructions designed to perform a specific computational task or solve a particular problem. It takes a set of inputs and transforms them into a desired output through a well-defined series of operations, ensuring that the process terminates in a finite amount of time.
Explain about big-oh notation.
Answer
Big-Oh notation (O-notation) is a mathematical tool used to describe the asymptotic upper bound of an algorithm's running time. It provides a worst-case scenario, ensuring that the algorithm will not perform worse than a specified growth rate for sufficiently large input sizes.
Formally, a function f(n) is said to be O(g(n)) if there exist positive constants c and n0 such that:
In this definition, g(n) acts as the upper bound for the growth rate of the function f(n). It is widely used in algorithm analysis to classify algorithms based on their efficiency, such as O(n), O(n log n), or O(n2), allowing for the comparison of performance independent of specific hardware or implementation details.
Define static space tree.
Answer
Sign in to view the complete answer paper.
Write and explain general iterative backtracking method.
Answer
Sign in to view the complete answer paper.
What is the time complexity of all pairs shortest path?
Answer
Sign in to view the complete answer paper.
Explain about OBST.
Answer
Sign in to view the complete answer paper.
What is Greedy method?
Answer
Sign in to view the complete answer paper.
Distinguish between Prim’s and Kruskal’s algorithms.
Answer
Sign in to view the complete answer paper.
Define branch and bound technique.
Answer
Sign in to view the complete answer paper.
Explain about non-deterministic algorithms.
Answer
Sign in to view the complete answer paper.
Part B
Write and explain the general method of divide-and-conquer strategy.
Answer
Sign in to view the complete answer paper.
Derive the time complexity of Strassen’s matrix multiplication.
Answer
Sign in to view the complete answer paper.
Write and explain recursive algorithm of binary search method.
Answer
Sign in to view the complete answer paper.
What is space complexity? Explain with suitable examples.
Answer
Sign in to view the complete answer paper.
Describe recursive formulation of backtracking technique.
Answer
Sign in to view the complete answer paper.
How to implement disjoint sets? Explain.
Answer
Sign in to view the complete answer paper.
Explain about 4-queens problem with backtrack solution.
Answer
Sign in to view the complete answer paper.
Discuss about number of connected components of a graph using disjoint set union.
Answer
Sign in to view the complete answer paper.
Use the 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) = (do, if, int, while) with p(1:4) = (3, 3, 1, 1) and q(0:4) = (2, 3, 1, 1, 1). Using the r(i, j)’s construct the optimal binary search tree.
Answer
Sign in to view the complete answer paper.
Discuss about all pairs shortest problem using dynamic programming.
Answer
Sign in to view the complete answer paper.
Compute a minimum cost spanning tree for the graph shown below using
Prim’s algorithm
Answer
Sign in to view the complete answer paper.
Kruskal’s algorithm.
Answer
Sign in to view the complete answer paper.
Explain about single source shortest path problem in Greedy method.
Answer
Sign in to view the complete answer paper.
Describe LC branch and bound solution of 0/1 Knapsack problem in detail.
Answer
Sign in to view the complete answer paper.
Nondeterministic knapsack algorithm
Answer
Sign in to view the complete answer paper.
FIFO branch and bound.
Answer
Sign in to view the complete answer paper.