3. (30 pts) The cashier's (greedy) algorithm for making change doesn't handle arbitrary denominations optimally. In this problem you'll develop a dynamic programming solu tion which does, but with a slight twist. Suppose we have at our disposal an arbitrary number of cursed coins of each denomination di, d2,..., dk, with di > d2 > dk and we need to provide n cents in change. We will always have dk = 1, so that we are assured we can make change for any value of n. The curse on the coins is that in any one exchange between people, with the exception of i-k-1, if coins of denomination di are used, then coins of denomination d+i cannot be used. Our goal is to make change using the minimal number of these cursed coins (in a single exchange, i.e., the curse applies). (a) (10 points) For i E1, k), n N, and b 0, 1), let C(i, n, b) denote the number of cursed coins needed to make n cents in change using only the last i denominations dk-i+1,dk-i+2, , dk, where dk-i+2 1s allowed to be used if and only if i 2 or b-0. That is, b is a Boolean "flag" variable indicating whether we are excluding the next denomination dk_i+2 or not (b 1 means exclude it). Write down a recurrence relation for C and prove it is correct. Be sure to include the base case (b) (10 points) Based on your recurrence relation, describe the order in which a dy- namic programming table for C(i, n, b) should be filled in. (c) (10 points) Based on your description in part (b), write down pseudocode for a dynamic programming solution to this problem, and give a bound on its running time (remember, this requires proving both an upper and a lower bound). 3. (30 pts) The cashier's (greedy) algorithm for making change doesn't handle arbitrary denominations optimally. In this problem you'll develop a dynamic programming solu tion which does, but with a slight twist. Suppose we have at our disposal an arbitrary number of cursed coins of each denomination di, d2,..., dk, with di > d2 > dk and we need to provide n cents in change. We will always have dk = 1, so that we are assured we can make change for any value of n. The curse on the coins is that in any one exchange between people, with the exception of i-k-1, if coins of denomination di are used, then coins of denomination d+i cannot be used. Our goal is to make change using the minimal number of these cursed coins (in a single exchange, i.e., the curse applies). (a) (10 points) For i E1, k), n N, and b 0, 1), let C(i, n, b) denote the number of cursed coins needed to make n cents in change using only the last i denominations dk-i+1,dk-i+2, , dk, where dk-i+2 1s allowed to be used if and only if i 2 or b-0. That is, b is a Boolean "flag" variable indicating whether we are excluding the next denomination dk_i+2 or not (b 1 means exclude it). Write down a recurrence relation for C and prove it is correct. Be sure to include the base case (b) (10 points) Based on your recurrence relation, describe the order in which a dy- namic programming table for C(i, n, b) should be filled in. (c) (10 points) Based on your description in part (b), write down pseudocode for a dynamic programming solution to this problem, and give a bound on its running time (remember, this requires proving both an upper and a lower bound)
