Design and Analysis of Algorithm Unit 3 – Divide and Conquer & Greedy Methods: important questions for AKTU
Unit 3 (Divide and Conquer & Greedy Methods) questions that AKTU repeats most often. This unit carries about 28 marks per paper. Start with the repeated questions, then the most asked topics.
Most repeated Unit 3 questions
- Explain Dijkstra's Algorithm. Prove that it may fail if the graph contains negative edge weights. (7 marks, 2026, Single Source Shortest Paths) – also asked in 2025, 2024, 2023, 2022, 2021, 2020, 2019
- Explain Kruskal's algorithm for MST and also discuss time complexity. (7 marks, 2026, Minimum Spanning Trees) – also asked in 2025, 2024, 2023, 2022, 2021, 2020, 2019
- 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) – also asked in 2026, 2024, 2023, 2022, 2021, 2020, 2019
Most important Unit 3 topic
- Divide and Conquer (Unit 3: Divide and Conquer & Greedy Methods) – asked 9 times in 2019, 2020, 2021, 2022, 2025, 2026
Most asked Unit 3 topics
- Divide and Conquer – asked 9 times
- Minimum Spanning Trees – asked 9 times
- Greedy Methods – asked 8 times
More 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)
- 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)
- 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)
Unit 3 syllabus topics
- Divide and Conquer
- Greedy Methods
- Minimum Spanning Trees
- Single Source Shortest Paths