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 sol- tion which does, but with a slight twist. Suppose we have at our disposal an arbitrary and we need to provide n cents in change We will always have d1, 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, wth the exception of a d, 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) k-1, if coins of denomination (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 prograrnming 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 sol- tion which does, but with a slight twist. Suppose we have at our disposal an arbitrary and we need to provide n cents in change We will always have d1, 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, wth the exception of a d, 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) k-1, if coins of denomination (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 prograrnming solution to this problem, and give a bound on its running time (remember, this requires proving both an upper and a lower bound)