3. Making Change Imagine you live in a country where the coin denominations are 1 cent, 4 cents, and 5 cents. Consider the problem where you are given some value n and you want to make change for this value, using the smallest number of coins. Part 1: Show that the greedy algorithm (use the largest value coins first) for making change fails for these denominations Part 2: Describe a dynamic programming algorithm for finding the smallest number of coins needed in this country to make change for any value of n. Analyze your algorithm. Part 3: Provide the running time of your algorithm