Design and Analysis of Algorithm Unit 3 – Divide and Conquer & Greedy Methods: AKTU previous year questions
34 AKTU questions from Unit 3 (Divide and Conquer & Greedy Methods) asked in 2019–2026, tagged by marks, year and topic. In short: about 28 marks of every paper come from this unit; the most asked topic is Divide and Conquer (9 times); 28 questions came back in a later year. The latest ones are listed below; on the page you can filter them by 2-mark or long questions, topic and repeats.
Unit 3 previous year questions
- 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)
- Apply the greedy single source shortest path algorithm on the graph given below. (7 marks, 2025, Single Source Shortest Paths)
- Write and explain the Kruskal’s algorithm to find Minimum Spanning Tree of a graph with a suitable example. (7 marks, 2025, Minimum Spanning Trees)
- Find the optimal solution of the fractional Knapsack problem with n=7 and the knapsack capacity of m=15. The profits and weights of the items are given below. Objects: 1 2 3 4 5 6 7 Profit (P): 5 10 15 7 8 9 4 Weight (w): 1 3 5 4 1 3 2 (7 marks, 2025, Greedy Methods)
- Define fractional Knap-Sack problem. (2 marks, 2024, Greedy Methods)
- Write name of Spanning tree algorithm with complexity. (2 marks, 2024, Minimum Spanning Trees)
- What do you mean by Activity selection problem? (2 marks, 2024, Greedy Methods)
- Describe DFS with its algorithm. How DFS can be used to solve the problem. (10 marks, 2024, Single Source Shortest Paths)
Most asked Unit 3 topics
- Divide and Conquer – asked 9 times
- Minimum Spanning Trees – asked 9 times
- Greedy Methods – asked 8 times
Unit 3 question pattern
- 2-mark questions: 10 asked in 2019–2026
- 7-mark questions: 13 asked in 2019–2026
- 10-mark questions: 11 asked in 2019–2026
- About 28 marks from Unit 3 in every paper
- 28 questions were asked again in a later year
Unit 3 questions year by year
- 2026: 4 Unit 3 questions asked (28 marks across that year's papers)
- 2025: 4 Unit 3 questions asked (23 marks across that year's papers)
- 2024: 5 Unit 3 questions asked (26 marks across that year's papers)
- 2023: 3 Unit 3 questions asked (30 marks across that year's papers)
- 2022: 5 Unit 3 questions asked (34 marks across that year's papers)
- 2021: 4 Unit 3 questions asked (32 marks across that year's papers)
- 2020: 5 Unit 3 questions asked (25 marks across that year's papers)
- 2019: 4 Unit 3 questions asked (23 marks across that year's papers)