Due to high demand the EECS Department decides to install a vending machine in the Bob and Betty Beyster Building, called the Bob and Betty Beyster Building Beverage Dispenser. Like any decent Beverage Dispenser the Bob and Betty Beyster Building Beverage Dispenser needs to provide change to customers after transactions and because this is a building filled with computer scientists, they wish the machine to return the smallest number of coins possible for any given amount of change. Due to space constraints the machine will only have space for three types of coins, 1, 3, and k. The EECS 376 student designing the machine decides that the machine will dispense the coins greedily (dispense the largest coin whenever possible), believing that this will always return the optimal number of coins. However, the student forgot the exact value of k (the student knows it is definitely 5c, though), and decided to build it using a Greedy algorithm anyway. (a) In this question we will guide you to proving that the Bob and Betty Beyster Building Beverage Dispenser will always return the optimal (smallest) number of coins, regardless the value you want change for. i. Fill in the blank to express "optimal" change-making mathematically: Let ni, n3, and nk be the number of I, 3e, and k coins, respectively, returned by an algorithm of change-making. In particular, the solution n1,n3, nis optimum iff we have ni + n3 + nk 2 ii. Using what you wrote for the previous question, prove that ni 2 111. For this question, assume k 5. Prove that there exists an optimal solution (n1, , nk) such that iv. Optional bonus. Show that for any integer k 2 5, there exists an optimal solution (n1, n3, nk) such that Hint: What is something that is common for the denominations where k 2 8? Complete the proof that the greedy algorithm must be optimal for all valid k. v. Assume the statement in part (iv), and recall that k is an integer with k 2 5 Hint: Write out the number of each coin, (nS,ng,n), returned by greedy algorithm to change a value of V. Proceed by using the previous results (assumed or proven) (b) In a parallel universe, the 5B Dispenser only has space for 1c, k and 11 coins, where k is an integer and 1