Question

Use the greedy algorithm to make change using quarters, dimes, nickels, and pennies for

a) 51 cents. b) 69 cents.

c) 76 cents. d) 60 cents.

Short answer

Subpart (a):

Hence, 51cents can be changed with 2 quarters and 1 pennies.

Subpart (b):

Hence, can be changed with 2 quarters, 1 dime, 1 nickel and 4 pennies.

Subpart (c):

Hence, 76 cents can be changed with 3 quarters and 1 penny.

Subpart (d):

Hence, 60 cents can be changed with quarters 2 and 1 dime.

Step-by-step solution

Subpart (a):

Step 1:

So, the conversion between U.S. coins are:

$$\begin{gathered} 1penny=1cents \\ 1nickel=5cents \\ 1dime=10cents \\ 1quarter=25cents \end{gathered}$$

Step 2:

So, by greedy change algorithm 51 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 2quarters=50cents \\ 1penny=1cent \end{gathered}$$

Therefore, 51cents can be changed with 2 quarters and 1 pennies.

Subpart (b):

Step 1:

So, the conversion between U.S. coins are:

$$\begin{gathered} 1penny=1cents \\ 1nickel=5cents \\ 1dime=10cents \\ 1quarter=25cents \end{gathered}$$

Step 2:

So, by greedy change algorithm 69 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 2quarters=50cents \\ 1dime=10cents \\ 1nickel=5cents \\ 4pennis=4cents \end{gathered}$$
Therefore, 69cents can be changed with 2 quarters, 1 dime, 1 nickel and 4 pennies.

Subpart (c):

Step 1:

So, the conversion between U.S. coins are:

$$\begin{gathered} 1penny=1cents \\ 1nickel=5cents \\ 1dime=10cents \\ 1quarters=25cents \end{gathered}$$

Step 2:

So, by greedy change algorithm 76 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 3quarters=75cents \\ 1penny=1cent \end{gathered}$$

Therefore, 76 cents can be changed with 3 quarters and 1 penny.

Subpart (d):

Step 1:

So, the conversion between U.S. coins are:

$$\begin{gathered} 1penny=1cents \\ 1nickel=5cents \\ 1dime=10cents \\ 1quarter=25cents \end{gathered}$$

Step 2:

So, by greedy change algorithm 60 cents can have following combinations of quarters, dimes, nickels, and pennies:

$$\begin{gathered} 2quarters=50cents \\ 1dime=10cents \end{gathered}$$

Therefore, 60 cents can be changed with 2 quarters and 1 dime.