Design and Analysis of Algorithm Unit 4 – Dynamic Programming, Backtracking & Branch and Bound: AKTU previous year questions
36 AKTU questions from Unit 4 (Dynamic Programming, Backtracking & Branch and Bound) asked in 2019–2026, tagged by marks, year and topic. In short: about 29 marks of every paper come from this unit; the most asked topic is Backtracking (13 times); 31 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 4 previous year questions
- 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)
- Illustrate the N-queens problem? Draw “State Space Tree” for 4 queen’s problem using backtracking. (7 marks, 2025, Backtracking)
- Find the optimal solution to the 0/1 Knapsack instances with n=4 and Knapsack capacity m=8 where profits and weights as follows : P={1, 2, 5,6} and W={2, 3, 4, 5} (7 marks, 2025, Dynamic Programming)
- Define the term "Graph Coloring". (2 marks, 2024, Backtracking)
- Apply Floyd-Warshall algorithm for constructing shortest path (10 marks, 2024, All Pair Shortest Paths)
- Determine an LCS of X={A,B,C,B,D,A,B} and Y={B,D,C,A,B,A} (10 marks, 2024, Dynamic Programming)
- Explain Backtracking. Let set S= {1,3,4,5} and X=8, we have to find subset sum problem using backtracking approach. (10 marks, 2024, Backtracking)
- Apply Branch and Bound technique to solve travelling salesman problem for the graph whose cost matrix given below. (10 marks, 2024, Branch and Bound)
Most asked Unit 4 topics
- Backtracking – asked 13 times
- Dynamic Programming – asked 10 times
- Branch and Bound – asked 8 times
Unit 4 question pattern
- 2-mark questions: 12 asked in 2019–2026
- 7-mark questions: 11 asked in 2019–2026
- 10-mark questions: 13 asked in 2019–2026
- About 29 marks from Unit 4 in every paper
- 31 questions were asked again in a later year
Unit 4 questions year by year
- 2026: 3 Unit 4 questions asked (21 marks across that year's papers)
- 2025: 4 Unit 4 questions asked (23 marks across that year's papers)
- 2024: 5 Unit 4 questions asked (42 marks across that year's papers)
- 2023: 7 Unit 4 questions asked (38 marks across that year's papers)
- 2022: 5 Unit 4 questions asked (34 marks across that year's papers)
- 2021: 4 Unit 4 questions asked (32 marks across that year's papers)
- 2020: 4 Unit 4 questions asked (23 marks across that year's papers)
- 2019: 4 Unit 4 questions asked (18 marks across that year's papers)