Chapter 16, Problem 1P

(a)

Program Plan Intro

To discuss the greedy algorithm in coin changing problem with pennies, dime, nickel, quarter and prove that greedy algorithm will give an optimal solution always.

Explanation of Solution

To prove that the changing problem of coin has an optimal solution, take ' n ' cent and suppose, for these ' n ' cent changes, there is an optimal solution. The solution takes a coin with value ' c ' and uses ' k ' coins. If the solution of ' n-c ' cent changes problem lies within the solution of ' n ' cent problem solution, that means ' k-1 ' coins are available for ' n-c ' cents. So, take the solution for the ' n-c ' cent changing problem and make sure this should be lesser then ' k- 1 ' coins then figure out the solution for ' n ' cent problem.

While dealing with ' n ' cent problem and try to get an optimal solution by taking minimum no. of coins. Always provide the biggest denomination coin until the rest amount became zero. So, if there is the biggest denomination present at first then by applying greedy methodology changes in quarter, dime, nickel and pennies are:

Q = ⌊ n /25 ⌋ quarter that gives n_Q = n mod 25 cent for change.

D = ⌊ n_Q /10 ⌋ dimes that gives n_D = n_Q mod 10 cent for change.

K = ⌊ n_D /10 ⌋ dimes that gives n_K = n_D mod 5 cent for change.

P = n_K pennies

By seeing the greedy solution, there are few possibilities like:

1. If n = 0; then zero coins in optimal solution.
2. If n > 0; then get the biggest denomination with value = ' n ' , suppose it’s ' c ' .
3. Now, take a coin and apply process in recursive manner for ' n-c ' cent.

To get the optimal solution through greedy algorithm, one must hold the coin ' c ' with value greater than ' n ' .

There are four cases needs to be considered here:

1. If (1= n < 5) then c = 1, this must hold the greedy choice and contains pennies.
2. If (5 = n = 10) then c = 5, by supposition, in this it must hold pennies and change 5 pennies to one nickel because this solution is not holding any nickel.
3. If (10 = n = 25) then c = 10, by supposition, it must hold a nickel and pennies but not a dime. So, add a dime in the solution.
4. If (25 = n ) then c = 25, by supposition, it holds a dime, pennies, and nickel but not quarter. If it has three dimes change it with a quarter and nickel and if has at least two dime then few subset of nickel, dime and pennies add nearly 25 cents and change these coins with a quarter to get a solution.

Here, for showing that it must contains an optimal solution with greedy choices and these choices will further helpful to get the solution of sub problem. Therefore, this greedy approach provides an optimal outcome for the given problem.

For an algorithm that selected a coin and recurses sub problem one by one, the running complexity will be θ ( k ), where ' k ' is the coins used for optimal solution. Now ( k = n), so, running time will be O ( n ) and there is only four type of coins. So, it requires O (1) constant time.

(b)

Program Plan Intro

To show that for given denomination ( c⁰, c¹, c², ........., c^k ), greedy algorithm always gives an optimal solution where ( c > 1) and (1 = k ).

Explanation of Solution

Take denomination c⁰, c¹, c², ........., c^k and changes amount ' n ' . By taking this, it is clear that

Only few coins are required in changing coin to give an optimal solution. Apply greedy algorithm, take biggest denomination coin first means take a denomination cⁱ (not c^k ), where ( k>i ).

1. To make sure that solution should be optimal take any denomination ( cⁱ ) no. of coin that must be lesser then ' c ' .
2. Take coins of ' cⁱ ' denomination having ( x₀, x₁, ...., x_k ) optimal solution and prove that for every ( k >i ), denomination ( c >x_i ).
3. And for few j , ( c = x_i ) and change denomination coins c_j with c_j+1coin .
4. Therefore, x_j reduced by c, x_j +1 increased by 1 and total no. of coins reduced by c -1.

This is contradicting about ( x₀, x₁,....., x_k ) being a solution. So, that optimal solution should have denomination ' c ' greater than xi for any ' cⁱ ' denomination.

Thus the only solution of the given problem is x_k = n/c_k ; for ( k>i ), x_i = n mod cⁱ +1/ cⁱ . Therefore this is proved that greedy algorithm with ( c⁰, c¹, c², ........., c^k ) denomination always gives an optimal solution.

(c)

Program Plan Intro

To prove that greedy algorithm does not provides the optimal solution all the time.

Explanation of Solution

Take the denomination set as {1, 3, 4} and the value of ' n =6’.

Then greedy solution will give two one cent coin {1, 1} and a four-cent coin {4} like {1, 1, 4} but two coins as {3, 3} is optimal solution.

So, for the set {1, 3, 4}, optimal solution will not present by using greedy algorithm.

In the other example where denomination set contains value {1, 10, 25}, for ' n = 30’; greedy algorithm provide a quarter and five pennies {25, 1, 1, 1, 1, 1} but the optimal solution should be three dime like {10, 10, 10}.

Thus, greedy algorithm will not provide an optimal solution always.

(d)

Program Plan Intro

To show that the time complexity of the algorithm is O ( nk ), where ' k ' is the total no. of coins.

Explanation of Solution

While applying the dynamic programming, take the demonstration ' d ' define as d₁ , d₂ , d₃ ,...., d_k and to make changes for ' i ' cent, no. of coins required min( c [ i ]). So, the minimum coins required can be calculated as:

c [ i ] = 1 + min{ c [ i-d_j ]}, if ( i > 0) and (1 = j = k ),

c [ i ] = 0, if ( i = 0)

This formula should be implemented as,

MakeChange ( d,n )

1. For ( i ← 1) to n
2. Do c [ i ] ← 8
3. For ( j ← 1) to k
4. Do if ( d_j = i )
5. Then if c [ i ] > c [ i-d_j ] + 1
6. Then c [ i ] ← c [ i - d_j ] + 1
7. denom[ i ] ← d_j
8. Return demon and ' c '

By seeing the algorithmic procedure of MakeChange( d,n ), it is showing that it requires two loops up to ' n ' times as outer loop and ' k ' times as inner loop.

Thus, the complexity of the implementation will be O ( nk ).