a$)(2$ points$)$ What is the greedy choice being made in the

make$-$change

algorithm?

$($b$)(4$ points$)$ Design a

non$-$canonical

coin system with $3$ coins,

$$

$=$

$($

$$

$1$

$,$

$2$

$,$

$3$

$)$

$.$ Show

that your system is not canonical by giving a counterexample.

$($c$)(8$ points$)$ Let

$,$

in

Z

$,$ both

$$

$2$

$.$ Prove that the system

$$

$=$

$($

$$

$$

$,$

$$

$$

$1$

$,...,,$

$1$

$)$

is canonical.

$($d$)(6$ points$)$ Prove that the American dollar bills

$$

$=$

$($

$100$

$,$

$50$

$,$

$20$

$,$

$10$

$,$

$5$

$,$

$2$

$,$

$1$

$)$

form a

canonical system.