a) What type of implementation is used in the algorithm given: top-down with memoization or bottom-up?...

 

Transcribed Image Text:

a) What type of implementation is used in the algorithm given: top-down with memoization or bottom-up? Hint: the notation K(w) used in the algorithm should NOT be interpreted as a function call, instead it should be treated as K[w], i.e., accessing table element using index w b) Rewrite the algorithm using recursive function without memoization. c) Comment on how this version of Knapsack problem is similar to rod cutting problem. For example, you can list that the given rod length n corresponds to the total weight the burglar can carry, W. Please identify all similar points between the two, and how the algorithms are also similar K(0) = 0 for w=1 to W: K(w) = max{K(w wi) + vi: w w} return K(W) a) What type of implementation is used in the algorithm given: top-down with memoization or bottom-up? Hint: the notation K(w) used in the algorithm should NOT be interpreted as a function call, instead it should be treated as K[w], i.e., accessing table element using index w b) Rewrite the algorithm using recursive function without memoization. c) Comment on how this version of Knapsack problem is similar to rod cutting problem. For example, you can list that the given rod length n corresponds to the total weight the burglar can carry, W. Please identify all similar points between the two, and how the algorithms are also similar K(0) = 0 for w=1 to W: K(w) = max{K(w wi) + vi: w w} return K(W)

Answer rating: 100% (QA)

Answer a The knapsack is a classic dyanamic programming problem In the algorithm below the bottom up approach is used i will explain how The given cod... View the full answer