Question

Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.

a. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c0 ; c1; …; ck for some integers c > 1 and k _ 1. Show that the greedy algorithm of picking the largest denomination first always yields an optimal solution. You are expected to reason about why this approach gives an optimal solution. (Hint: Show that for each denomination ci, the optimal solution must have less than c coins.)

b. Design an Ο(nk) time algorithm that makes a change for any set of k different coin denominations, assuming that one of the coins is 3 cents in value.

Answer 1

The greedy algorithm for making change with coins whose denominations are powers of an integer >1 is optimal because using fewer coins of a larger denomination is always better than using more of a smaller one. For arbitrary coin denominations, an O(nk) time complexity dynamic programming algorithm can be designed.

Step-by-step explanation:

Optimal Coin Change Solution with Powers of c

The goal is to make change for n cents using the fewest number of coins with denominations that are powers of c, where c is an integer greater than 1. The greedy algorithm, which selects the largest denomination of coin first, is optimal in this scenario. This is because for any denomination ci, using c or more coins of a smaller denomination would add up to at least the value of one coin of denomination ci+1, which would not minimize the number of coins. Given that the successive denominations are multiples of each other by a factor of c, there's no need for more than c-1 coins of a smaller denomination between two larger denominations. Consequently, the largest denomination coin will always be used until it exceeds the remaining change to be given, ensuring an optimal solution.

Algorithm for Change with Arbitrary Denominations

For a set of k arbitrary coin denominations, including a 3-cent coin, an algorithm to make change for n cents can run in O(nk) time. This algorithm involves dynamic programming where we construct a table dp with the size n+1. Each entry dp[i] will hold the minimum number of coins needed to make change for i cents. The algorithm iteratively updates the table based on the minimum coins needed, considering each denomination available. Since we iterate over n values for each of the k denominations, the overall time complexity is O(nk).

Answer 2

a) Proof:

1. Let’s consider the first two types of coins in this set, pennies and coins that are worth c cents each, which we will call c^ . At most, we can use c −1 pennies because any number larger than c pennies would be replaced by at least one c^ coin. This operation would reduce the total coin number by c −1. In other words, when the remainder is greater than c and I’m allowed to use only pennies and c^ coins, I would use as many c^​​​​​​​ coins before considering pennies.

2. The same thoughts apply for larger coins. Let’s consider c^ ​​​​​​​n-1 and \hat{c}​​​​​​​n coins. At most, we can use c −1 c^ ​​​​​​​n-1 coins. Because any number larger than cn would be replaced by at least one \hat{c}​​​​​​​n coin. This operation would reduce the total coin number by c −1. In other words, when the remainder is greater than c^ ​​​​​​​n and I’m allowed to use only coins that are worth less than c^ ​​​​​​​n , I would use as many \hat{c}​​​​​​​n coins as possible before considering other coins.

3. Combining the first two arguments, the greedy algorithm applies to all the levels of this particular coin set denomination.

b) The greedy algorithm always provides a solution but doesn’t guarantee the smallest number of coins used. The greedy algorithm takes O(nk ) for any kind of coin set denomination, where k is the number of different coins in a particular set. The algorithm is implemented below in Java:

/** * Makes change using a recursive Greedy algorithm. * * param amount * The amount of change to make. * param coins * The sorted set of coins, ordered from smallest to largest. * return The number of coins used to make the change. */ int makeChangeGreedyStyle(int amount, int[] coins) { // Check if there is no more change to make. if (amount == 0) { System.out.println(""); return 0; } // Loop over the change in order of greatest to smallest. for (int i = coins.length; i > 0; i--) { int coin = coins[i - 1]; // If the next largest coin is found, print out its value. if (amount >= coin) { System.out.print(coin + " "); return 1 + makeChangeGreedyStyle(amount - coin, coins); } } // Arriving here means it's impossible to make change // using this greedy algorithm, this amount of change, // and this set of coins. System.out.print("Cannot make change; "); System.out.println("cents remaining: " + amount); return 0; }

Step-by-step explanation: