Question $1$

Trace the dynamic programming algorithm for the coin$-$row problem for the following row of $7$ coins: $\{7,3,5,10,8,6,9,4\}.$ Fill in all the table values and list all the optimal solutions.

Question $2$:

Trace the dynamic programming algorithm for the change$-$making problem for the denominations $1,2,3,4,5,$ and the amount n $=14.$ Fill in all the table values and list all the optimal solutions.

Question $3$:

Trace the dynamic programming algorithm for the longest common subsequence problem with strings X$[1..\mathrm{.}4]=$bacb$$ and Y$[1..\mathrm{.}6]=$abcabc$.$ Complete all the entries in the table below, and also build all of the optimal solutions.

$012345$

$0$

$1$

$2$

$3$

$4$

Question $4$

Trace the dynamic programming algorithm for the $0-1$ knapsack problem using size n$=4$ and capacity W$=6,$ and with benefit values b$[1..\mathrm{.}4]$ and weights w$[1..\mathrm{.}4]$ as shown. Complete all the entries in the tables below, and also indicate how to find all the optimal solutions in the table

k $1234$

bk $3486$

wk $1364$

k w $0123456$

$0$

$1$

$2$

$3$

$4$

Question $5$

Trace the dynamic programming algorithm of the optimal BST for $5$ keys A$,$ B$,$ C$,$ D$,$ E with search probabilities $0\mathrm{.}1,0\mathrm{.}2,0\mathrm{.}3,0\mathrm{.}4,$ and $0\mathrm{.}5,$ respectively. Complete all the entries in the table below, and also show how to find all the optimal solutions.

i j $012345$

$1$

$2$

$3$

$4$

$5$

$1$

$2$

$3$

$4$

$5$

$6$