Dynamic Programming Algorithms

• Floyd’s algorithm

21.5 Assignment #9 (due We, Dec 1)

1. Show the tree of memory states traversed by our recursive permutation algorithm for input “a,b,c,d”.
2. Provide a recursive backtracking algorithm for the vertex cover problem.
3. Provide a branch-and-bound algorithm for the 0/1 knapsack problem.
4. Provide a dynamic programming algorithm for the coin exchange problem.