Exercise 2 (20 points plus 5 bonus points). Dynamic Programming (+ Greedy) For this part of the assignment, we will solve a very common day-to-day problem. What is the smallest number of coins required to dispense exactly an amount that is owed? This question can always be solved by using a Dynamic Programming algorithm; however, for certain coin systems (as the Canadian), this question can be answered quicker by running a greedy approach. This greedy approach involves repeatedly choosing a coin of the largest denomination that is less than or equal to the amount still owed, until the amount owed reaches zero. As a Comp251 student, you have been commissioned to: Given a coin system C={c1,c2,,cn}, determine whether a greedy algorithm will always give an optimal solution or not. For this problem, we will work under the following restrictions: - The number of denominations n in the coin system is greater than 1 and less than 101 (i.e., 1