Please write any code in C++ if needed.

PART 2: Greedy Algorithm 1. Given that you have coins in 1 cent, 5 cent, 10 cent, 25 cent and 1 dollar (100 cents) form. Develop a greedy algorithm pay the customer with the smallest number of coins. For example, 28 cents can be paid by using one 25 cent coin, 3 one cent coins. You have to describe the algorithm and implement it (Submit the code) (20) 2. Prove that your algorithm does indeed give the correct answer (20) 3. For some coin denominations the greedy algorithm may not work. One possible example is if the denominations are (1,3 and 4) cents. Give two other sets of denominations where the greedy algorithm will not work, and give instances where they fail. [HINT: Try to pick denominations that are not multiples of each other] (5*2=10)