Problem 3. Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer. Problem 3.a. (4 points) Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c',c,....ck for some integers c >1 and k > 1. Show that the greedy algorithm of picking the largest denomation first always yields an optimal solution. You are expected to reason about why this approach gives an optimal solution. (Hint: Show that for each denomination c', the optimal solution must have less than c coins.) Problem 3.b. (4 points) Design an Onk) time algorithm that makes change for any set of k different coin denomina- tions, assuming that one of the coins is a penny. Problem 4. (7 points) Implementation: Implement the make change algorithm you designed in the previous problem. Your program should read a text file "data.txt" where each line in "data.txt" contains three values c, k and n. Please make sure you take your input in the specified order c, k and n. For example, a line in "data.txt" may look like the following: 3 438 where c = 3, k = 4, n = 38. That is, the set of denominations is (30, 31, 32, 33, 34} = {1,3,9, 27,81}, and we would like to make change for n = 38. The file "data.txt" may include multiple lines like above. The output will be written to a file called "change.txt", where the output corresponding to each input line contains a few lines. Each line has two numbers, where the first number denotes a de- nomination and the second number represents the cardinality of that denomination in the solution. For example, for the above input line 3 4 38', the optimal solution is the multiset {27,9,1,1}, and the output in the file "change.txt" is as follows: 27 1 91 12 which means the solution contains 1 coin of denomination 27, one coin of 9 and two coins of denomination 1. You can use a delimiter line to separate the outputs generated for different input lines