Design and Analysis of Algorithm (BCS503) AKTU previous year questions 2019–2026
Every Design and Analysis of Algorithm question from 8 AKTU papers, tagged by unit, topic and marks. A few recent questions from each unit are listed below; open the page to filter by unit, topic or mark type.
Unit 1: Introduction: Algorithms and Sorting – AKTU PYQs
- Define algorithm and its characteristics. (2 marks, 2026, Algorithm Analysis Basics)
- Compute the time complexity of the following recurrence relation. T(n)= √n T(√n) + n if n>2 = 2 if n=2. (2 marks, 2026, Algorithm Analysis Basics)
- 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, 2026, Comparison Based Sorting)
- Define growth of functions. (2 marks, 2026, Algorithm Analysis Basics)
- Compute the time complexity of the following recurrence relation. T(n) = 2T(n-1) + n if n>1 = 1 if n=1. (7 marks, 2026, Algorithm Analysis Basics)
Unit 2: Advanced Data Structures – AKTU PYQs
- What is a Persistent Data Structure? (2 marks, 2026, Persistent Data Structures)
- 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, 2026, Red-Black Trees)
- Explain Fibonacci Heap with suitable example. (7 marks, 2026, Fibonacci Heaps)
- 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, 2026, Skip List)
- List the properties of Binomial Heap (2 marks, 2025, Binomial Heaps)
Unit 3: Divide and Conquer & Greedy Methods – AKTU PYQs
- 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? (7 marks, 2026, Minimum Spanning Trees)
- 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, 2026, Divide and Conquer)
- Explain Kruskal's algorithm for MST and also discuss time complexity. (7 marks, 2026, Minimum Spanning Trees)
- Explain Dijkstra's Algorithm. Prove that it may fail if the graph contains negative edge weights. (7 marks, 2026, Single Source Shortest Paths)
- With a suitable example explain the concept of Convex –Hull Problem (2 marks, 2025, Divide and Conquer)
Unit 4: Dynamic Programming, Backtracking & Branch and Bound – AKTU PYQs
- 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, 2026, Dynamic Programming)
- Explain the Branch and Bound approach for the Travelling Salesman Problem (TSP) using the Reduced Cost Matrix method. (7 marks, 2026, Branch and Bound)
- Given a 3 x 3 cost matrix, calculate the initial Lower Bound using the row-reduction method. (7 marks, 2026, Branch and Bound)
- With a suitable example explain “Branch and Bound”. (2 marks, 2025, Branch and Bound)
- Write Floyd’s and Warshal’s algorithm to find all pair shortest path in a graph. Discuss its time complexity. (7 marks, 2025, All Pair Shortest Paths)
Unit 5: Selected Topics – AKTU PYQs
- Define Polynomial-time Verifiability. (2 marks, 2026, NP-Completeness Theory)
- 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, 2026, String Matching)
- Describe the Boyer-Moore string matching algorithm. How do the bad character and good suffix heuristics work? (7 marks, 2026, String Matching)
- Describe “Randomized algorithms”. List few randomized algorithms. (2 marks, 2025, Randomized Algorithms)
- Explain Vertex Cover Problem. Solve vertex cover problem using approximation algorithm (7 marks, 2025, Approximation Algorithms)