You are a cashier at a store, and you need to give change to a customer for a specific

amount using the fewest possible coins. You have an unlimited supply of coins with

denominations of $1,5,10,12,25,$ and $50$ cents. Suppose a customer needs change of $64$

cents. What will be the greedy choice property selected by the cashier, and what coins will

be given to the customer? Will the greedy algorithm always provide the optimal solution

for every change amount using the given denomination of coins? Justify your answer with

the help of a suitable explanation.

$($b$)$ Solve the following recurrence relation using the master method:

$(4)$

$(3)$

T$($n$)=2$T $(1+\text{'}/$n $,$ where T$(1)=1$