Computational Thinking (CO2412) Tutorial 2.2: Calendar Week 45

2.2. Cashier problem

The cashier problem is specified as follows. The function solving the problem has two arguments:

• first, a natural number, given in the smallest currency unit (e.g., pence), representing an amount of money that is to be paid out
• second, a sorted list containing the values of the existing coin types, in the same currency unit

As the function's return value, we expect:

• a list containing coin values that add up to the requested amount; this must be the shortest possible list, i.e., we want to use as few coins as possible

Note that as a precondition it is assumed that the list passed as the function's second argument is already sorted.

Greedy algorithm for the cashier problem

A greedy algorithm for this problem starts with an empty list (of coins). It keeps appending that list by the largest possible coin, without ever exceeding the requested amount. Eventually, the requested amount is reached, and the finalized list is returned. In the greedy cashier notebook, this is implemented as follows:

def cashier(amount, coin_types):
    coins = []
    remainder = amount
    while remainder >= coin_types[0]:
        for i in range(len(coin_types)-1, -1, -1):
            if remainder >= coin_types[i]:
                coins.append(coin_types[i])
                remainder -= coin_types[i]
                break
    return coins

Above, the expression range(len(coin_types)-1, -1, -1) is used to traverse the list in reverse order, beginning with the greatest coin type.

Role of the coin system

In the notebook, this is applied to two coin systems, the conventional one, [1, 2, 5, 10, 20, 50, 100, 200], and an alternative one, [1, 8, 27, 64, 125, 216, 343, 512]. For an amount given as 93, the greedy algorithm returns [50, 20, 20, 2, 1] for standard coins and [64, 27, 1, 1] for the alternative coins.

Discussion: We know from experience that the algorithm above works correctly for the conventional coin system, i.e., it returns the shortest possible list of coin values adding up to any integer number. Does it work correctly for the alternative coin system? If it does not, what would be a counterexample?

1. How would you express a condition that needs to be applied to the coin system such that the greedy algorithm is guaranteed to work correctly?
2. What design strategy would you apply for the general case, covering any possible coin system? Describe the algorithm that you would develop (an implementation is not required, but welcome) and explain why it solves the problem correctly (a rigorous proof is not required, but welcome).
3. Discuss the efficiency of your general algorithm and compare it to the efficiency of the greedy algorithm in the case of coin systems where both are correct.

To avoid the case where an integer value cannot be produced by a coin system at all, it can be assumed that the value 1 is always included among the existing coin types.

Submission deadline: 27^th November 2021; discussion planned for 9^th December 2021. Group work by up to four people is welcome.