Tackle this problem using the dynamic programming technique. The problem that we will consider is the so called coin changing problem $.$ Consider the problem of developing an algorithm that will

determine how many of each type of coin,such as quarters, dimes and so forth, it

takes to equal the given amount such that the number of coins used is minimal.

Let us assume that the coins available are dollars, quarters, dimes,

nickels and pennies only. For example, $77$ cents can be changed to $3$ quarters and

two pennies. The number of coins used is $5$ and you should convince yourself that we

can not total $77$ cents with less than $5$ coins.

To tender change for a given amount with the minimum number of coins we would

first like to give out as many quarters as possible. For the remaining amount we would

like to give out as many dimes as possible, and so on$.$ Finally we hand out pennies for

whats left. This method comes naturally and instinctively to us$.$ We may have done

it before without realizing that we were handing out the minimum possible number

of coins for the amount in question. Computer scientists call this method the greedy

method. The basic method

is to grab as much as possible at every step in the solution.

As we proved in class, with the given values for the coins, this greedy algorithm

always produces an optimal solution to our problem. However, with a different series

of values for the coins, the greedy algorithm may not work.

Suppose the country of Weirdonia has three types of coins worth $1$ cent, $9$ cents

and $10$ cents. To make up an amount of $36$ cents, the greedy algorithm would use

$9$ coins $(3$ coins of $10$ cents each and $6$ coins of $1$ cent each$).$ One could actually do

better, by using $4$ coins of $9$ cents each.

We can develop an algorithm using dynamic programming that always works, no

matter what the values of the coins are. You are going to do that for this problem.

But, I will guide you through the process so that you don$$t get overwhelmed.

Suppose the currency we are using has available coins of n different denominations.

Let a coin of denomination i$,1$ i $$ n$,$ have value di$.$ We assume that each di $>0.$

Further, we assume that the denominations are presented to us in increasing order

i$.$e$.,$ d$1$ d$2$ d dn$.$ Finally, we assume that d$1$ is $1$ so that it is feasible

to make up any amount. Let m be the amount for which we want to determine the

minimal num of coins needed.

Define c$[$i$,$ j$]$ to be the minimum number of coins required to pay an amount of j

units, $0$ j $$ m$,$ using only coins of denomination $1$ to i$,1$ i

$4.$ Design an improvised recursive algorithm to solve the same problem that ensures

that no subproblem is solved more than once. Basically maintain an appropriate

table and use the memoization technique. This is also sometimes called as the

top down approach. $(4$ Pts$.)$

$5.$ In practice, even when there are no repeated subproblems recursive implemen$-$

tations involves considerable overhead as the system has to set up stack space

etc. Hence, non$-$recursive implementations are often preferred even if the worst

case complexity is the same. Design an algorithm using the bottom up approach

for solving the same problem using the dynamic programming technique.

$6.$ Illustrate the operation of your bottom up algorithm by means of the following

example. The different denominations available are $1$ cent, $4$ cents and $6$ cents.

The amount that we are concerned with is $15$ cents. Show, the entire table and

do not just give me the final answer.

$7.$ What is the complexity of your bottom up algorithm? Is this a polynomial time

algorithm or not? If so$,$ why so and If not, why not? $(3$ Pts$.)$

$8.$ Assuming that the table C$[1..$n$,0..$m$]$ is already built, devise an algorithm to

determine an optimal solution to the coin changing problem. Note that the

algorithms that you developed in the previous part only computed the value

of an optimal solution and not an optimal solution itself. Specifically, your

algorithm should output an integer array X$[1..$n$]$ with the property that X$[$i$]$

is the number of coins of ith denomination that could be used while disbursing

an amount of m cents optimally. $(3$ Pts$.)$

$9.$ What is the complexity of the algorithm that you designed to produce an opti$-$

mal solution? $(3$ Pts$.)$

$10.$ Normally speaking, the bottom up algorithms are preferred as they don$$t involve

the overhead of recursion. However, for this problem there is an important dis$-$

advantage of the bottom up algorithm in comparison to the top down algorithm.

Can you identify and elucidate it$?(3$ Pts$.)$

to make up any amount. Let m be the amount for which we want to determine the

minimal number of coins needed.

Define c$[$i$,$j$]$ to be the minimum number of coins required to pay an amount of j

units, j m$,$ using only coins of denominations $1$ to i i n$.$ Now, carry

out the following steps.

Develop a recurrence relation for c$[$i$,$j$]$ by analyzing the structure of the opti$-$

mal solution. You need to specify clearly the recurrence relation and the base

condition. Y