Question $1.$ Apply the bottom$-$up dynamic programming algorithm to the following instance

of the $\frac{0}{1}-$knapsack problem, with capacity $=6$ and five items with weights: $3,2,1,4,5$ and

values: $25,20,15,40,50.$

$F(i,j)=$max$\{F(i-1,j),v_i+F(i-1,j-w_i)\}ifj-w_{i}0$

$=F(i-1,j)\{\begin{array}{ccc}\text{:}& if& j-w_{i}0\end{array}$

$F(0,j)=0$ and $F(i,0)=0$

Question $2.$ The rod$-$cutting problem consists of a rod of $n$ units long that can be cut into

integer$-$length pieces. The sale price of a piece i units long is $$ for $i=1,$dots,$n.$ We want to

find the maximum total sale price of the rod by apply dynamic programming to the rod$-$cutting

problem. Let $F(k)$ be the maximum price for a given rod of length $k.$

$.$ Give the recurrence on $F(k)$ and its initial condition$($s$).$

$.$ What are the time and space efficiencies of your algorithm?

Now, consider the following instance of the rod$-$cutting problem: a rod of length $n=5,$ and the

following sale prices $P1=2,P2=3,P3=7,P4=2$ and $P5=5.$

$.$ Explain the execution of your dynamic programming algorithm $($in particular portray the

computations of the different entries of the table$)$ and give its solution $($the total price and

the actual cuts$).$

Question $3.$ True or false: When use dynamic programming to solve the knapsack issue,

the sequence of values of each row is nondecresing.

Question $4.$ True or false: When use dynamic programming to solve the knapsack issue,

the sequence of values of each column is nondecresing

Question $5.$ True or false: The root of an optimal binary search tree always contains the

key with the highest search probability

Question $6.$ Given a number $N,$ you've to find the number of different ways to write it as

the sum of $1,4$ and $5.$

For example, if $N=6,$ the answer would be $6.$

$1+1+1+1+1+1$

$.1+1+4$

$1+4+1$

$.4+1+1$

$.5+1$

$\mathrm{.}1+5$

Find dynamic$-$programming solution for this problem.