Problem $5$:

PART$-$A:

Consider the following change$-$making problem: The input to this problem is an integer L$.$The output should be the minimum cardinality collection of coins required to make L shillings of change, that is$,$ you want to use as few coins as possible. The coins are worth $1,5,10,20,25,$ and $50$ shillings. Assume that you have an unlimited number of coins of each type. Formally prove or disprove that the greedy algorithm that takes as many coins as possible from the highest denominations correctly solves the problem. So$,$ for example, to make a change for $234$ Shillings, the greedy algorithm would require ten coins: four $50$ shilling coins, one $25$ shilling coin, one $5$ shilling coin, and four $1$ shilling coins.

PART$-$B :

Consider another change$-$making problem: The input to this problem is again an integer L$,$ and the output should again be the minimum cardinality collection of coins required to make L nibbles of change $($that is$,$ you want to use as few coins as possible$).$ Now the coins are worth $1,2,2^2,2^3,...,2^1000$ nibbles. Assume that you have an unlimited number of coins of each type. Prove or disprove that the greedy algorithm that takes as many coins of the highest value as possible solves the change$-$making problem.

Hint: The greedy algorithm is correct for one of the above two subproblems and is incorrect for the other. For the problem where greedy is correct, use the following proof strategy: Assume, to reach a contradiction, that there is an input I on which greedy is not correct. Let OPT$($I$)$ be a solution for input I that is better than the greedy output G$($I$).$ Show that the existence of such an optimal solution OPT$($I$)$ that is different than greedy is a contradiction. So what you can conclude from this is that for every input, the output of the greedy algorithm is the unique optimal$/$correct solution.