Based on this algorithm, answer the following questions:

Given denominations d = (d, d2, ..., dn) and an amount N to be paid, determine the number of coins in each denomination necessary to disburse N units using the fewest possible coins. Assume that there is an unlimited supply of coins in each denomination. a. Write pseudo-code for a greedy algorithm that attempts to solve this problem. (Recall that the greedy strategy doesn't necessarily produce an optimal solution to this problem. Whether it does or not depends on the denomination set d.) Your algorithm will take the array d as input and return an array G as output, where G[i] is the number of coins of type i to be disbursed. Assume the denominations are arranged by increasing value d 1, and 1 sis n, i.e. d = (1, b, b2, ..., bn-1). Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter-example. c. Let d = 1 and 2di s di+1 for 1 si sn - 1. Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter- example. tvoros CoinChange(d.N) 1. n = length[d] 2. for i = 1 ton 3. C[i,0) = 0 4. for i = 1 ton for j = 1 to N if i = 1 and j 1, and 1 sis n, i.e. d = (1, b, b2, ..., bn-1). Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter-example. c. Let d = 1 and 2di s di+1 for 1 si sn - 1. Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter- example. tvoros CoinChange(d.N) 1. n = length[d] 2. for i = 1 ton 3. C[i,0) = 0 4. for i = 1 ton for j = 1 to N if i = 1 and j