The problem that we will consider is the so called coin changing problem that

we discussed in class. 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.

To begin with 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. It is no surprise that such a method comes naturally to us humans!. The greedy method is often employed to solve many an apparently intractable problems in computer science and you would be surprised how often it works. 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$3<...<$ 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 number 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 denominations $1$ to i$,1$ i $$ n$.$ Now, carry

out the following steps.

$1.$ 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. You should also justify as to why they are correct. $(8$ Pts$.)$

$2.$ Using the recurrence relation developed, write a simple recursive algorithm to

compute c$[$i$,$ j$].$ Note that, by simply calling this recursive algorithm with pa$-$

rameters n and m$,$ we can determine the minimum number of coins needed to

pay an amount of m units using the available coins of n different denominations.

$(4$ Pts$.)$

$3.$ The English coinage before decimalization included half$-$crowns $(30$ pence$),$

florins $(24$ pence$),$ shillings $(12$ pence$),$ sixpences $(6$ pence$)$ and pennies. The

coinage also included several other coins such as farthing and three pence, but

we will ignore them to limit the number of denominations to $5.$ Suppose, I want

to dispense an amount of $48$ pence using the coinage of $5$ different denomina$-$

tions, we will call your recursive program with parameters $(5,48).$ Draw the

complete recursion tree generated by this call. For each node in the tree, sim$-$

ply write the parameters of that recursive call. c$(5,48)$ will be the root of the

recursion tree. Observe that it involves lots of repeated subproblems. Clearly,

mark the repeated subproblems in your recursion tree. If a bigger subproblem is

repeating, do not worry about marking the repetitions of the sub$-$subproblems

of that bigger subproblem. $(4$ Pts$.)$

Typically the simple implementation would have terrible computational com$-$

plexity as it involves solving repeated subproblems. Dynamic programming

method is to avoid doing solving repeated subproblems and in this part you

will build an implementation for the coin changing problem using the dynamic

programming technique.

$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$.)$