$(15$ points$)$ Mr E has a question about his Jar of Change. After putting in $n$ cents, $($b$)$ Identify a set of Euro coin denominations $($a subset of the denominations here$)$

$1$ for which the greedy algorithm does not yield an optimal solution for making

change. Justify your answer in terms of optimal substructure and the greedy$-$

choice property. $($The set should include the $1$ Euro cent so that there is a solution

for every value of $n.)$ Include an example where the cashier's algorithm with your

choice of denominations yields a set of coins that is larger than it needs to be$,$

and also show the smaller set of coins adding up to the same value.

he can always get out $n$ cents using the smallest number of coins $($in other words, it

implements the coin change problem$).$

$($a$)$ MrE tells you that he always wondered how it worked, so he asked his deamon

$Al$ to explain it$.$ Al claimed it used a greedy algorithm called "the cashier's

algorithm" and wrote the following pseudocode:

Suppose we have coins with denominations of $v[1]>v[2]>$cdots$>v[r]$ for $r$ coins

types, where each coin's value $v[i]$ is a positive integer. Then the smallest number

of coins needed to represent $n$ cents is change $(n,v,r)$ :d$[1..$ r$]=1//$ initial histogram of coin types in solution k $=$ r if k$==0\{$ return $\text{'}$no solution' $\}\}$

This code has bugs $($you think Al might be an LLM$).$ Identify the bugs and explain

why each would cause the algorithm to fail.