Design and Analysis of Algorithm Unit 4 Notes AKTU (BCS503)

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Unit 4 · Notes

AKTU Design and Analysis of Algorithm (BCS503) Unit 4 notes for B.Tech Semester 5 – Dynamic Programming, Backtracking & Branch and Bound. Topics: Dynamic…

Open the interactive reader to study this resource on AcademicArk.

Unit 4: Dynamic Programming, Backtracking & Branch and Bound – AKTU syllabus topics

  • Dynamic Programming: Knapsack Problem, Resource Allocation Problem, Longest Common Subsequence, Principle of Optimality
  • All Pair Shortest Paths: Warshall's Algorithm, Floyd's Algorithm
  • Backtracking: N-Queen Problem, Graph Coloring, Sum of Subsets, Hamiltonian Cycles
  • Branch and Bound: Travelling Salesman Problem, Hamiltonian Cycles

Most asked AKTU PYQ questions from Unit 4

  1. Q5a. 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, 2025-26)
  2. Q6a. Explain the Branch and Bound approach for the Travelling Salesman Problem (TSP) using the Reduced Cost Matrix method. (7 marks, 2025-26)
  3. Q6b. Apply Branch and Bound technique to solve travelling salesman problem for the graph whose cost matrix given below. (10 marks, 2023-24)
  4. Q1f. With a suitable example explain “Branch and Bound”. (2 marks, 2024-25)
  5. Q1g. Differentiate Backtracking and Branch and Bound Techniques. (2 marks, 2022-23)
  6. Q1d. Differentiate Backtracking algorithm with branch and bound algorithm. (2 marks, 2020-21)
  7. Q6a. Illustrate the N-queens problem? Draw “State Space Tree” for 4 queen’s problem using backtracking. (7 marks, 2024-25)
  8. Q1h. Explain Branch and Bound method in brief. (2 marks, 2021-22)
  9. Q5b. Explain Backtracking. Let set S= {1,3,4,5} and X=8, we have to find subset sum problem using backtracking approach. (10 marks, 2023-24)
  10. Q2d. Apply Floyd-Warshall algorithm for constructing shortest path (10 marks, 2023-24)

AKTU paper codes: BCS503, KCS503, RCS502

Other Design and Analysis of Algorithm units

Design and Analysis of Algorithm previous year papers

More Design and Analysis of Algorithm resources

Browse all notes · Semester 5 notes