JNTU
JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (July/August - 2023 - R16)
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
Define θ-notation and Omega notation.
Answer
θ-notation (Theta) provides a tight bound on the growth rate of a function, such that f(n) = θ(g(n)) if there exist positive constants c1, c2, and n0 such that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0. Ω-notation (Omega) provides an asymptotic lower bound, such that f(n) = Ω(g(n)) if there exist positive constants c and n0 such that f(n) ≥ cg(n) for all n ≥ n0.
How do you measure the algorithm running time?
Answer
Algorithm running time is measured by counting the number of primitive operations (like additions, comparisons, or assignments) executed as a function of the input size n. This is typically expressed using asymptotic notation (Big-O, Ω, or θ) to represent the worst-case, average-case, or best-case performance, often by analyzing the frequency of execution of the most dominant code segment.
What is a set? List the operations that can be performed on it.
Answer
Sign in to view the complete answer paper.
State and explain graph coloring problem.
Answer
Sign in to view the complete answer paper.
Define greedy method.
Answer
Sign in to view the complete answer paper.
What are the drawbacks of greedy method?
Answer
Sign in to view the complete answer paper.
State the principle of optimality.
Answer
Sign in to view the complete answer paper.
Write about reliability designing.
Answer
Sign in to view the complete answer paper.
Define NP-Complete.
Answer
Sign in to view the complete answer paper.
Why the search path in a state-space tree of a branch and bound algorithm is terminated?
Answer
Sign in to view the complete answer paper.
Part B
What is an algorithm? Explain its characteristics.
Answer
Sign in to view the complete answer paper.
Derive the time complexity of quick sort in an average case.
Answer
Sign in to view the complete answer paper.
Discuss about time complexity in detail.
Answer
Sign in to view the complete answer paper.
Write the algorithm for merge sort with an example.
Answer
Sign in to view the complete answer paper.
Write an algorithm to determine the Hamiltonian cycle in a given graph using backtracking.
Answer
Sign in to view the complete answer paper.
Discuss about AND/OR graph problem with an example.
Answer
Sign in to view the complete answer paper.
Give the solution to the 8-queens problem using backtracking.
Answer
Sign in to view the complete answer paper.
Write and explain the algorithm of Bi connected components with an example.
Answer
Sign in to view the complete answer paper.
Write and explain prim’s algorithm for generating minimum cost Spanning tree and list some applications of it.
Answer
Sign in to view the complete answer paper.
Explain the greedy technique for solving the Job Sequencing problem.
Answer
Sign in to view the complete answer paper.
What are the applications of greedy method? Discuss.
Answer
Sign in to view the complete answer paper.
Explain the time and space complexity of Dynamic Programming traveling sales person algorithm.
Answer
Sign in to view the complete answer paper.
Write and explain the algorithm of matrix chain multiplication.
Answer
Sign in to view the complete answer paper.
Explain the all pairs shortest path problem with an example.
Answer
Sign in to view the complete answer paper.
Write an algorithm of OBST.
Answer
Sign in to view the complete answer paper.
Show that the Hamiltonian path problem is NP-Complete.
Answer
Sign in to view the complete answer paper.
Is the travelling salesman problem is NP-hard or NP-Complete? Justify your answer.
Answer
Sign in to view the complete answer paper.
Write an algorithm of FIFO Branch and Bound.
Answer
Sign in to view the complete answer paper.
Discuss in detail about Cook’s theorem.
Answer
Sign in to view the complete answer paper.