This exercise is to gain an hands$-$on understanding of implementing a Dynamic Programming

algorithm from the recursive formulation. Consider the $0/1$ Knapsack problem and the recursive

formulation developed in Section $6\mathrm{.}6.$ Your pseudocodes and implementations below should

faithfully follow this recursive formulation.

$1.$ Give pseudocode for a DP algorithm $($i$.$e$.,$ iterative, bottom$-$up$).$

$2.$ Give pseudocode for a recursive $($i$.$e$.,$ top$-$down$)$ algorithm. Your recursive algorithm should

have two versions: the first one, without memoization and the second, with memoization.

That is$,$ you should give two different pseudocodes, one for each version.

$3.$ Implement all your pseudocodes in Python $($preferred$)$ or C$++($less preferred$).$

$4.$ Run all your algorithms on the following input for the knapsack problem. Let the number

of items, n $=20$ and let knapsack capacity be m $=200.$ Each of the item gets a random

integer weight from $1$ to $100.$ Run at least $10$ instances of the above input, where in each

instance n and m are the same, but the weights of the items are newly generated randomly

in each instance.

$5.$ Compare the run times of the three implementations $($one iterative and the two recursive$)$

on all the inputs. Present your results in a table.