Just Problem $3$: Provide a dynamic programming solution to each problem by following the described steps.

You need to complete steps $($a$),($c$),($d$),$ and $($e$)$ for all $3$ problems, but it will suffice to complete

steps $($b$)$ and $($f$)$ only for one of the problems:

Steps:

$($a$)$ Identify the "last" decision you need to make to compute the value of the optimal solution.

For example, for rod cutting, the last decision we need to make is the length of the first cut

we will make.

$($b$)$ Define and prove optimal substructure. This entails applying the statement "the solution to

the larger problem cannot use suboptimal solutions to subproblems" to the specific problem

in hand.

$($c$)$ Define subproblems $($i$.$e$.,$ the table you are trying to compute$),$ express the value of the

optimal solution for the overall problem in terms of the values of the optimal solutions to

subproblems.

$($d$)$ Formulate a recursive solution to compute the value of the optimal solution for subproblems.

Do not forget to specify the base case$($s$).$

$($e$)$ Characterize the runtime of the resulting procedure assuming that you would implement your

solution using a bottom$-$up procedure.

$($f$)$ Provide the pseudo code of the bottom$-$up procedure you use to compute the value of the

optimal solution, as well as the procedure for reconstructing the optimal solution. As an

exercise that will help connect the abstract solution here to a real computer program, you

may also want to implement this procedure using a programming language of your choice and

test your code. But this is up to you and you do not need to submit anything in that regard.

Problems:

$(1)$ We are given an arithmetic expression $x_1{o}_1{x}_2{O}_{2}dots{x}_{n-1}{o}_{n-1}{x}_n$ such that $x_i$ for $1in$ are

positive numbers and $o_{i}in\{+,\}$ for $1in-1$ are arithmetic operations $($summation or

multiplication$).$ We would like to parenthesize the expression in such a way that the value of

the expression is maximized. For example, if the expression is $3+42+60\mathrm{.}5,$ then the

optimal parenthesization is $(3+4)(2+(60\mathrm{.}5)),$ with a value of $35.$

$(2)$ We are given $n$ types of coin denominations with integer values $v_1,v_2,$dots,$v_n.$ Given an

integer $t,$ we would like to compute the minimum number of coins to make change for $t($i$.$e$.,$

we would like to compute the minimum number of coins that add up to $t,$ where repetitions

are allowed$).$ We know that one of the coins has value $1,$ so we can always make change for

any amount of money $t.$ For example, if we have coin denominations of $1,2,$ and $5,$ then the

optimal solution for $t=9$ is $5,2,2.$

$(3)$ Given two strings $x=$ and $Y=,$ the edit distance between

$x$ and $Y$ is defined as the minimum number of edit operations $($replacement$,$ insertion, or

deletion of a character$)$ required to convert $x$ to $Y.$ For example, the edit distance between

$x=$ esteban and $Y=$ stephen is $4,$ comprising of $1$ deletion $(e),1$ insertion $(h),$ and $2$

replacements and $ae).$ We would like to compute the edit distance between two

given strings.