Question

I want to design an algorithm decides on the notes to give a customer at a cash dispensing machine. The machine only has $20 and $50 notes and I want my algorithm to dispense the minimum number of notes to the customer. This means that if a customer wants $120 then the machine will dispense two $50 notes and one $20 note rather than six $20 notes.

I propose an algorithm to solve this problem.

My algorithm is:

input: amount  (the amount of cash that is needed)
output: notes (set of notes)
while  amount is greater than $50
   subtract $50 from amount
   add $50 note to notes
end while

while amount is greater than zero dollars
   subtract $20 from amount
   add $20 note to notes
end while

if amount is less than $0 
    print error message "can't give change for that amount"
else
    print out the content of notes
end else

This algorithm is incorrect in the sense that, for some values it will print out the error message:

"can't change amount"

for some values that can actually be changed with just $20 and $50 notes. List three values of amount under $251 for which the algorithm will behave incorrectly.

What is a simple correction you could make to the algorithm to make it distribute change correctly ? (1 mark)

Answer 1

Three values for which the algorithm behaves incorrectly are

• $60
  • Here, algorithm dispenses $50 first and reaches $10. Since there is no way to dispense $10, it prints the error message. But the right way to dispense cash was [$20, $20, $20]
• $80
  • Here, algorithm dispenses $50 first and reaches $30. It dispenses a $20 and reaches $10. Since there is no way to dispense $10, it prints the error message. But the right way to dispense cash was [$20, $20, $20, $20]
• $110
  • Here, algorithm dispenses $50 two times to reach $10. Since there is no way to dispense $10, it prints the error message. But the right way to dispense cash was [$50, $20, $20, $20]

If we look carefully, problem arises when we reach the amount $60 or $80. Though both the amounts are greater than $50, we need not dispense $50 at that point but dispense a $20. This will ensure algorithm distributes change correctly. So a simple change can be introduced in the algorithm as follows -

while amount is greater than $50 but not equal to $60 or $80
   subtract $50 from amount
   add $50 note to notes
end while

while amount is greater than zero dollars
   subtract $20 from amount
   add $20 note to notes
end while

if amount is less than $0
   print error message "can't give change for that amount"
else
   print out the content of notes
end else