JNTU
JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (January/February - 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 Big ‘Oh’ notation.
Answer
Big 'Oh' notation, denoted as O(g(n)), represents the asymptotic upper bound of a function. A function f(n) belongs to O(g(n)) if there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c · g(n) for all n ≥ n0. It describes the worst-case time complexity of an algorithm, providing an upper limit on the growth rate of the running time as the input size n increases.
Compare Quick Sort and Merge Sort.
Answer
Quick Sort and Merge Sort are both divide-and-conquer algorithms, but they differ significantly in their approach and performance characteristics:
- Strategy: Quick Sort uses a pivot-based partitioning strategy, sorting the array in-place by rearranging elements around the pivot. Merge Sort uses a recursive divide-and-conquer strategy, splitting the array into halves, sorting them, and then merging the sorted sub-arrays.
- Time Complexity: Quick Sort has an average-case time complexity of O(n log n) but a worst-case of O(n²), which occurs when the pivot selection is poor. Merge Sort guarantees O(n log n) time complexity in all cases (best, average, and worst).
- Space Complexity: Quick Sort is an in-place algorithm requiring O(log n) auxiliary space for the recursion stack. Merge Sort is not in-place and typically requires O(n) auxiliary space to store the temporary sub-arrays during the merge process.
- Stability: Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. Quick Sort is generally considered unstable.
What is an articulation point in a graph? Give an example.
Answer
Sign in to view the complete answer paper.
Construct the state space tree for 4-Queens problem with bounding function.
Answer
Sign in to view the complete answer paper.
Write an algorithm for simple Union operation.
Answer
Sign in to view the complete answer paper.
What is Minimum Spanning Tree? Give an example.
Answer
Sign in to view the complete answer paper.
Write the difference between the Dynamic programming and the Greedy method.
Answer
Sign in to view the complete answer paper.
What is mean by state space tree? Give an example.
Answer
Sign in to view the complete answer paper.
Define cook’s theorem.
Answer
Sign in to view the complete answer paper.
Draw the relation of P, NP, NP-Hard and NP-Complete.
Answer
Sign in to view the complete answer paper.
Part B
Sort the following data using Quick Sort and illustrate each step with appropriate figure for each iteration. [ 20, 12, 35, 15, 11, 19, 35 ]
Answer
Sign in to view the complete answer paper.
Write the Recurrence relation and derive the best case complexity for the Quick Sort.
Answer
Sign in to view the complete answer paper.
Describe asymptotic notations Big Oh (O), Omega (Ω) and Theta (Ɵ) notations and show their behavior using graphical representation.
Answer
Sign in to view the complete answer paper.
Give the asymptotic bounds for the equation
Answer
Sign in to view the complete answer paper.
Generate the state space tree and find the solutions for the subset sum for N=7, m=35, w={5,7,10,12,15,18,20} using back tracking approach.
Answer
Sign in to view the complete answer paper.
Write an algorithm for Graph Coloring problem and explain with an example.
Answer
Sign in to view the complete answer paper.
Explain the concept of minimum cost spanning tree? What are the different algorithms exist for obtaining minimum cost spanning tree. Compute the minimum cost spanning tree using Prim’s algorithm for the given graph. Draw the spanning tree generated at each step.
Answer
Sign in to view the complete answer paper.
Write greedy algorithm for knapsack problem. Find the solution for the following Knapsack problem using greedy method. (p1,p2,p3,p4)=(2,5,8,1), (w1,w2,w3,w4)=(10,15,6,9) and m=30.
Answer
Sign in to view the complete answer paper.
Write an algorithm for all pairs shortest path. Define its complexity.
Answer
Sign in to view the complete answer paper.
Compute the shortest distance between each pair of nodes for the following graph using all pair shortest path algorithm.
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),
Answer
Sign in to view the complete answer paper.
Generate the state space tree using FIFO Branch and Bound and find the shortest path followed by the travelling salesperson instance defined by the cost matrix given below.
Answer
Sign in to view the complete answer paper.
Explain circuit satisfiability problem with a circuit diagram. Show that circuit satisfiability problem is NP- hard.
Answer
Sign in to view the complete answer paper.