Consider the coin changing problem --- You are given some coins of different denominations say (1, 2, 3, ... , ) (all of them in cents) and you need to make a certain sum by picking the smallest number of coins. The following questions pertains to this problem

Design a greedy algorithm that solves this problem.

With a set of denominations (1,5,10,20,50) and = 37 what is the solutionreturned by the greedy algorithm? What is the optimal solution in this case?

With a set of denominations (1,5,10,20,25) and = 40 what is the solution returned by the greedy algorithm? What is the optimal solution in this case?