Home › AKTU PYQ › Design and Analysis of Algorithm › Important Questions › Unit 4

Design and Analysis of Algorithm Unit 4 – Dynamic Programming, Backtracking & Branch and Bound: important questions for AKTU

Unit 4 (Dynamic Programming, Backtracking & Branch and Bound) questions that AKTU repeats most often. This unit carries about 29 marks per paper. Start with the repeated questions, then the most asked topics.

Most repeated Unit 4 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) – also asked in 2025, 2024, 2023, 2022, 2021, 2020, 2019
  • Explain the Branch and Bound approach for the Travelling Salesman Problem (TSP) using the Reduced Cost Matrix method. (7 marks, 2026, Branch and Bound) – also asked in 2025, 2024, 2023, 2022, 2021, 2020, 2019
  • Apply Branch and Bound technique to solve travelling salesman problem for the graph whose cost matrix given below. (10 marks, 2024, Branch and Bound) – also asked in 2026, 2023, 2022, 2021, 2020, 2019

Most important Unit 4 topic

  • Backtracking (Unit 4: Dynamic Programming, Backtracking & Branch and Bound) – asked 13 times in 2019, 2021, 2022, 2023, 2024, 2025

Most asked Unit 4 topics

  • Backtracking – asked 13 times
  • Dynamic Programming – asked 10 times
  • Branch and Bound – asked 8 times

More Unit 4 previous year questions

  • 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)

Unit 4 syllabus topics

  • Dynamic Programming
  • All Pair Shortest Paths
  • Backtracking
  • Branch and Bound