6) a) In the Coin changing problem, we have to give change for n rupees using the least number of coins of a given set of denominations. It is clear that we cannot give change for any n for all set of denominations. For example, trivially, we cannot give change for . 3, if no 1, 2 or 3 rupees coins do not exist or not included in the allowed denominations. If the set of denominations include l then we can always give change, so that there is a way of changing n for any n. We can use greedy approach to find the optimal solutions for many set of denominations. Show that, however, there are set of denominations for which we cannot find the optimal solution by greedy approach. You should include l in your denominations so that a solution always exists for the