1. Recall the coin changing problem: 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. 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 dy 1, and 1 sisn, 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 sisn - 1. Does the greedy strategy always produce an optimal solution in this case? Either prove that it does, or give a counter example