Standard 10: Greedy Algs 1: Algorithms

Short description: Construct and execute greedy algorithms; identify failures of greedy.

Relevant notes: Topic D: Greedy Algorithms.

Full description

Given problems like knapsack and interval scheduling, define and execute greedy algorithms. Given problems where greedy is not optimal, identify failures and provide counterexamples to optimality.

Example problem

Part a.

You are a cashier making change. You have a supply of quarters (worth 25 cents), dimes (worth 10 cents), nickels (worth 5 cents) and pennies (worth 1 cent). Given an amount, such as 87 cents, your goal is to make change using as few coins as possible.

Give a greedy algorithm for this problem. Walk through the execution of your algorithm on the example input of 87.

Part b.

Now you are making change in a strange world where you have a supply of florins, shillings, and pennies. Florins are worth 13 cents, shillings are worth 8 cents, and pennies are still worth 1 cent. Given an amount, your goal is to make change using as few coins as possible.

First, describe the greedy algorithm that you used in Part a, translated to this setting of florins and shillings. Then, prove that the greedy algorithm is not optimal. Your proof should use a counterexample.

Sample solution

Sample solution.

Part a. We use as many quarters as possible until the amount remaining is less than 25 cents. Then we use as many dimes as possible until the amount remaining is below 10 cents. Then we use a nickel if possible, so the amount remaining is below 5 cents. Then we use pennies for the remaining amount.

On input 87:

We use 3 quarters for 75, leaving 12 cents left.
We use 1 dime, leaving 2 cents left.
We don't use any nickels.
We use 2 pennies.

Part b. The greedy algorithm would be to use as many florins as possible until the remainder is less than 13 cents, then use a shilling if possible so that the amount is under 8 cents, then use pennies.

This greedy algorithm fails on the example input of 16. The correct minimum number of coins needed is two: two shillings. However, the greedy algorithm would first use one florin, then three pennies for a total of four coins.

Rubric

Rubric.

To pass, a solution must pass both parts.

To pass, a solution must follow the course requirements for writing.

To pass Part a, the solution must clearly describe the greedy algorithm, i.e. that we use as many quarters as possible first, etc. It must give the correct answer for the example. For Part b, the algorithm must correctly identify the greedy algorithm and must give a correct counterexample. It must explain what the greedy algorithm does on the counterexample and what the optimal solution is, i.e. why greedy is suboptimal.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct, clear, concise.
3 (Pass, Proficient): correct, possibly not fully clear, may contain a more lengthy or roundabout description. In Part a, the solution to the example is correct, but may not be very clearly presented or explained. In Part b, the descriptions may leave out small details as long as the answer is clear in the context of Part a.
2 (Fail, Progress): In Part a, may have a mistake in the greedy algorithm definition or in the example solution. In Part b, may have an incorrect counterexample, or may not clearly show that greedy is suboptimal on the counterexample. May contain a significant amount of unnecessary description or commentary.
1 (Fail, Wrong Track): Does not appear to be using the correct greedy algorithm.