Design and Analysis of Algorithm PYQ 2025-26 AKTU Question Paper

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Session 2025-26 · PYQ

AKTU Design and Analysis of Algorithm previous year question paper 2025-26 for B.Tech Semester 5. Covers Introduction: Algorithms and Sorting, Advanced Data…

Open the interactive reader to study this resource on AcademicArk.

Design and Analysis of Algorithm AKTU syllabus

  1. Unit 1: Introduction: Algorithms and Sorting
  2. Unit 2: Advanced Data Structures
  3. Unit 3: Divide and Conquer & Greedy Methods
  4. Unit 4: Dynamic Programming, Backtracking & Branch and Bound
  5. Unit 5: Selected Topics

Questions in Design and Analysis of Algorithm AKTU PYQ 2025-26

  1. Q1a. Define algorithm and its characteristics. (2 marks, 2025-26)
  2. Q1b. Compute the time complexity of the following recurrence relation. T(n)= √n T(√n) + n if n>2 = 2 if n=2. (2 marks, 2025-26)
  3. Q1c. Find the total number of comparisons after using the Insertion sort on the following array. Array A= {23, 32, 40, 44, 54, 63, 72, 89}. (2 marks, 2025-26)
  4. Q1d. What is a Persistent Data Structure? (2 marks, 2025-26)
  5. Q1e. Define growth of functions. (2 marks, 2025-26)
  6. Q1f. In a Red-Black Tree, how many black nodes are there on any path from the root to the leaf if the black height is 3? (2 marks, 2025-26)
  7. Q1g. Define Polynomial-time Verifiability. (2 marks, 2025-26)
  8. Q2a. Compute the time complexity of the following recurrence relation. T(n) = 2T(n-1) + n if n>1 = 1 if n=1. (7 marks, 2025-26)
  9. Q2b. Let P be a Quick Sort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Find the number of t1 and t2. (7 marks, 2025-26)
  10. Q2c. Provide the decreasing order of asymptotic complexity of functions f1, f2, and f3 and justify your answer: f1(n) = n^{k log n}, f2(n) = n^{1000}, and f3(n) = k^{n log k}, where k is a very large constant. (7 marks, 2025-26)
  11. Q2d. Explain Merge Sort with example and also compute time complexity. (7 marks, 2025-26)
  12. Q2e. Explain Fibonacci Heap with suitable example. (7 marks, 2025-26)
  13. Q3a. Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. W_ij in the matrix W below is the weight of the edge {i, j}. What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T? 0 1 8 1 4 1 0 12 4 9 8 12 0 7 3 1 4 7 0 2 4 9 3… (7 marks, 2025-26)
  14. Q3b. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4, and F5 are of dimensions 2x25, 25x3, 3x16, 16x1 and 1x1000, respectively. Find the optimal parenthesization and total number of scalar multiplications. (7 marks, 2025-26)
  15. Q4a. In a Skip List, if the probability of a node being promoted to the next level is 1/2, what is the expected number of nodes at the second level if there are 100 nodes at the base level? (7 marks, 2025-26)
  16. Q4b. Explain Kruskal's algorithm for MST and also discuss time complexity. (7 marks, 2025-26)
  17. Q5a. Solve a 0/1 Knapsack problem with given profits [60, 100, 120, 90, 75, 45], weights [5, 10, 15, 20, 35, 40] and capacity = 50 using Dynamic Programming. (7 marks, 2025-26)
  18. Q5b. Explain Dijkstra's Algorithm. Prove that it may fail if the graph contains negative edge weights. (7 marks, 2025-26)
  19. Q6a. Explain the Branch and Bound approach for the Travelling Salesman Problem (TSP) using the Reduced Cost Matrix method. (7 marks, 2025-26)
  20. Q6b. Given a 3 x 3 cost matrix, calculate the initial Lower Bound using the row-reduction method. (7 marks, 2025-26)
  21. Q7a. Using Rabin-Karp algorithm, how many hash computations are needed to search for a pattern of length 4 in a text of length 15? (7 marks, 2025-26)
  22. Q7b. Describe the Boyer-Moore string matching algorithm. How do the bad character and good suffix heuristics work? (7 marks, 2025-26)

AKTU paper codes: BCS503, KCS503, RCS502

Design and Analysis of Algorithm previous year papers

More Design and Analysis of Algorithm resources

Browse all notes · Semester 5 notes · Design & Analysis of Algorithm notes