Module 4: Dynamic Programming Approach

Edit Answers
12345678910111213141516171819202122232425262728
Across
  1. 2. A rectangular arrangement used to store values during dynamic programming computations
  2. 7. An algorithmic technique that solves a problem using solutions to smaller subproblems
  3. 8. A dynamic programming approach that solves smaller subproblems before larger ones
  4. 10. A longest subsequence common to two given sequences
  5. 12. The amount of capacity occupied by an item
  6. 13. A representation of a particular subproblem in dynamic programming
  7. 15. The maximum weight that a knapsack can hold
  8. 16. A knapsack problem in which each item is either selected or not selected
  9. 18. A structure used to store solutions to subproblems
  10. 19. A smaller problem whose solution contributes to the solution of the original problem
  11. 21. A problem of selecting items to maximize total value within a weight limit
  12. 24. A group or level of vertices in a multistage graph
  13. 25. A path between two vertices having minimum total cost
  14. 26. A route that visits every city and returns to the starting city
  15. 27. The cost of a shortest path between two vertices
  16. 28. The benefit obtained by selecting an item in the knapsack problem
Down
  1. 1. Subproblems that occur repeatedly within a problem
  2. 2. A graph in which vertices are divided into a sequence of stages
  3. 3. Describes shortest-path computation between every pair of vertices
  4. 4. The property of a solution that gives the best possible result
  5. 5. A problem of finding a minimum-cost tour that visits every city exactly once
  6. 6. A vertex considered between a source and destination while computing shortest paths
  7. 9. A sequence obtained by deleting elements without changing the order of the remaining elements
  8. 11. A property in which an optimal solution contains optimal solutions to its subproblems
  9. 14. A dynamic programming approach that solves a problem recursively and stores computed results
  10. 17. An algorithm that finds shortest paths between all pairs of vertices
  11. 20. The best value obtained for a particular dynamic programming subproblem
  12. 22. An equation that expresses a solution in terms of solutions to smaller subproblems
  13. 23. A location represented as a vertex in the Travelling Salesperson Problem