3. (30 pts) The cashiers (greedy) algorithm for making change doesnt handle arbitrary denominations optimally. In this problem youll 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 d1,d2,...,dk, with d1 > 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 di+1 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 {1,...,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 dki+1, dki+2, . . . , dk, where dki+2 is 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 dki+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).