3. Due to high demand, the EECS Department has finally decided to install a vending machine, called the Bob and Betty Beyster Building Beverage Bestower. Like any decent vending machine, the B6 must provide change to customers after purchases. Because this is a building teeming with computer scientists, the machine should return the smallest number of coins possible for any given amount of change. Due to design constraints, the machine only has space for three types of coins: l, 4, and 174. The student designing the machine (who did not take EECS 376) decides that it should use a greedy algorithm to dispense change Specifically, it first returns as many 174 coins as it can (without overpaying), then as many 4 coins as it can, then the appropriate number of 1c coins. The student hopes that this strategy will always return an optimal (smallest) number of coins; in this question, you (an EECS 376 student) will prove that this is indeed the case. (a) Let c denote the amount of change and let ni, n4 and n 17 respectively denote the number of 14, 4, and 174 coins returned by the greedy algorithm. Likewise, let ning and niz denote the number of 1, 4, and 174 coins in an optimal solution. That is, the sum ni +n + ni is minimal.) i. Show that n* n17 and conclude that niz = N17. iv. Similarly, conclude that na = n4. Hint: Use the previous parts. v. Conclude that ni = ni. That is, the greedy algorithm outputs an optimal solution (b) In a parallel universe, the B6 only has space for 1, kc and 17c coins, where k is an integer strictly between 1 and 17. Find a k such that the greedy approach does not return the optimal number of coins for every amount of change. Note that you just proved in (a) that with k = 4 the greedy algorithm gives the optimal answer. (c) Although the student designing the B6 is sad that the greedy algorithm will not always work for dispensing change in this universe, you (an EECS 376 student) have learned that you can find the optimal number of coins for any set of coin denominations using dynamic programming. Write base case(s) and the recurrence relation for computing OPT-COIN-CHANGE(C), where C is the amount of change you want to make. You can only use 1c, kc and 17c coins (k is the value you found in (b)). Briefly justify why this will be optimal regardless of denominations