Algorithm design styles

Why this matters

An algorithm is a set of steps that turns an input into an output. Most problems can be solved by more than one set of steps, and the sets are not equal. One may be correct but slow. Another may be fast but give a wrong answer for some inputs. A third may be fast and correct, but only after you have checked the right things.

Beginners often pick the first idea that comes to mind and stop there. This lesson shows three common ways to design an algorithm and applies all three to the same small problem. You will see where each one is right, where each one fails, and how to tell which one to trust.

The lesson uses the tools from the earlier lessons in this module: plain steps, pseudocode and trace tables. Measuring two algorithms against each other on paper is covered in the lesson Comparing two algorithms on paper; here the goal is to see the three styles, not to measure them carefully.

One problem, three ways

Before a design style can be shown, there has to be a problem. Here is a small one.

A shop sells items with price tags, and the owner wants to pay a bill using as few coins as possible. A coin is a single piece of money, and each coin has a fixed value, such as 1, 3 or 4 units. The owner has a set of coin values, called the coin set, and an amount to pay.

Take the coin set [1, 3, 4] and the amount 6. The question is: what is the smallest number of coins that adds up to exactly 6?

Work it out by hand first. You can pay 6 with six coins of value 1. You can pay 6 with a 4 and two 1s, which is three coins. You can pay 6 with two 3s, which is two coins. Two coins is the smallest possible answer, because one coin cannot be 6. So the answer is 2.

Keep that answer in mind. Each of the three styles below must be checked against it.

Style 1: brute force

Brute force means trying every possible answer or every possible combination, and keeping the best one. It does not need cleverness. It needs only a complete list of what to try.

Think of a combination lock with three dials of ten digits each. A brute force attack tries 000, 001, 002 and so on up to 999. It is slow, but it cannot miss the right code, because every code is tried.

For the coin problem, a brute force method tries every sequence of coins that adds up to 6. Each sequence is one way to pay. The method keeps the sequence with the fewest coins.

Here is the method in pseudocode. The word best holds the smallest count found so far, and it starts empty.

set best to nothing
function try(remaining, used):
    if remaining is 0:
        if best is nothing or used is less than best:
            set best to used
        stop this branch
    for each coin in the coin set:
        if coin is not more than remaining:
            try(remaining minus coin, used plus 1)
call try(amount, 0)

The function try is a recursive function. It is a function that calls itself with a smaller problem. Each call takes one coin away from remaining and adds one to used. The function stops a branch when remaining reaches 0, which means the coins chosen so far pay the amount exactly.

Here is the same method in Python. Python is a programming language that reads close to plain English, and it is the language used for the examples in this lesson. The code also counts how many complete ways it checked, so you can see how much work the method does.

The output is:

fewest coins: 2
complete ways checked: 9

The answer is 2, which is correct. The program checked 9 complete ways to pay 6. Those 9 ways are: 1,1,1,1,1,1, four orderings of 1,1,1,3 (the 3 can sit in any of four places), 3,3, and three orderings of 1,1,4. Counting them gives 1 + 4 + 1 + 3 = 9.

The method is correct, and the reason is simple: every possible way was tried. A brute force method cannot give a wrong answer for a problem that has a finite number of answers to try. The price is the amount of work. The number of ways grows very fast as the amount grows. With the coin set [1, 3, 4], an amount of 6 gives 9 ways, but the same method on an amount of 15 with the coin set [1, 4, 6, 10] checks 155 ways, and an amount of 63 with the coin set [1, 5, 10, 25] has far too many ways to check in a short time. The script for this lesson skips that last case for that reason.

Style 2: greedy

Greedy means making the choice that looks best right now, and never going back to change it. A greedy method takes one step at a time. At each step it picks the option that gives the most benefit immediately.

A real-life example is a person filling a shopping trolley with the most expensive item first, then the next most expensive, until the money runs out. That person does not check every possible set of items. They make one choice after another, and each choice is locally the best.

For the coin problem, the greedy choice is the largest coin that still fits. Take that coin, subtract it from the amount, and repeat.

sort the coin set from largest to smallest
set chosen to an empty list
set remaining to amount
for each coin in the sorted list:
    while coin is not more than remaining:
        add coin to chosen
        set remaining to remaining minus coin
if remaining is 0:
    the answer is chosen

Here is the greedy method in Python.

The output is:

greedy chose: [4, 1, 1]
number of coins: 3

Greedy gives 3 coins. The correct answer is 2 coins. Greedy is wrong for this coin set.

The mistake is easy to see once the steps are written out. Greedy took the 4 first, because 4 was the largest coin that fit. That choice left 2, and the only coins left were 1s, so it had to use two 1s. A better first choice was 3, which leaves 3, and 3 is one more coin that finishes the job. Greedy never looked at that option, because it never goes back to change a choice.

The method is fast. It makes one pass through the coins, and for each coin it does a few steps. A greedy method is usually much faster than brute force. The price is that a greedy method is correct only when the problem has a special structure that makes the local best choice also the global best one. For the common coin set [1, 5, 10, 25], the greedy answer happens to be the best answer. The script in this lesson shows that case below. It does not prove the method works in general, and beginners should not assume it does.

Run this check in the same script to see both results side by side:

The output is:

[1, 5, 10, 25], amount 63: [25, 25, 10, 1, 1, 1]
[1, 3, 4], amount 6: [4, 1, 1]

The first line gives 6 coins, and 6 is the fewest possible for that case. The second line gives 3 coins, and 2 is the fewest. The same method is right in one case and wrong in the other.

Style 3: search the answer

Search the answer means guessing a possible answer and checking whether it works. You try the answers in some order, and you stop at the first one that works. The search does not build the answer step by step. It asks a yes or no question about each guess: is this answer possible?

A real-life example is finding the lowest shelf height from which a book can be reached with a stool of a given height. You try heights one at a time, from the lowest. For each height you ask, can I reach the book from here? The first height that works is the answer.

For the coin problem, the guess is the number of coins. Start with a guess of 1 coin. Ask: can the amount be paid with at most 1 coin? If not, try 2 coins. Ask again. Stop at the first guess that works.

The yes or no question needs its own small method. Here is the question written as pseudocode.

function can_pay(amount, coins_left):
    if amount is 0:
        yes, the amount is paid
    if coins_left is 0:
        no, there are no coins left to use
    for each coin in the coin set:
        if coin is not more than amount:
            if can_pay(amount minus coin, coins_left minus 1) is yes:
                yes
    no

Then the search itself is a loop over guesses.

set guess to 1
while guess is not more than amount:
    if can_pay(amount, guess) is yes:
        the answer is guess
        stop
    add 1 to guess

Here is the full method in Python.

The output is:

fewest coins for 6 with [1, 3, 4]: 2

The search gives the right answer. Here is what it did, one guess at a time.

Guess 1: can 6 be paid with at most 1 coin? The method tries each coin. Coin 1 leaves 5 with no coins left, which fails. Coin 3 leaves 3 with no coins left, which fails. Coin 4 leaves 2 with no coins left, which fails. The answer to the question is no.

Guess 2: can 6 be paid with at most 2 coins? Coin 1 leaves 5 with one coin left, and no single coin makes 5, so this branch fails. Coin 3 leaves 3 with one coin left. Coin 3 takes that coin, and 3 minus 3 is 0, so the amount is paid. The answer is yes. The search stops and returns 2.

The search is correct for the same reason brute force is correct. It checks every possible number of coins in order, and it stops at the first one that works. It cannot skip the right answer, because the smallest possible answer is found first.

The cost depends on how many guesses it takes. The method above starts at 1 and counts upward. If the answer is large, many guesses fail before the right one, and each guess runs its own check. A faster version uses binary search, which halves the range of guesses each time. That is a topic for a later module. In this lesson, the point is that the search asks a yes or no question about a guess, and it checks the guesses in an order that makes the first yes the best answer.

Running all three on one bill

Here is a second and a third example, to see the three styles on cases that are not so easy. The first case is the one above. The second case uses the coin set [1, 4, 6] and the amount 8. The third case uses the coin set [1, 4, 6, 10] and the amount 15.

Put the three methods in one script and run it.

The output is:

coins [1, 3, 4] amount 6
  brute force: fewest = 2 ways checked = 9
  greedy:       [4, 1, 1] count = 3
  search:      fewest = 2
coins [1, 4, 6] amount 8
  brute force: fewest = 2 ways checked = 10
  greedy:       [6, 1, 1] count = 3
  search:      fewest = 2
coins [1, 4, 6, 10] amount 15
  brute force: fewest = 3 ways checked = 155
  greedy:       [10, 4, 1] count = 3
  search:      fewest = 3

Look at the second case. The coin set is [1, 4, 6] and the amount is 8. Greedy takes the 6 first, then two 1s, which is 3 coins. The best answer is two 4s, which is 2 coins. Greedy is wrong again, for the same reason as before: it took the largest coin that fit, and that left a remainder that needed extra coins.

Look at the third case. Greedy gives 3 coins, and the best answer is also 3 coins. Greedy is right here, but the lesson does not depend on that. The fact that greedy gets lucky on one input does not make it a correct method. The brute force and search methods are the ones that give the right answer for every input in this list, because they check every option or every possible number of coins in order.

The table below gives the comparison in short form.

The table is short on purpose. A real comparison of the amount of work needs a count of steps on paper, which is the subject of the lesson Comparing two algorithms on paper.

Choosing a style

Start by asking whether the problem has a small number of answers to try. If it does, brute force is the safest first design, because it is easy to check against the rules. Write it first, run it on small cases, and keep it as a reference.

Next, ask whether the local best choice can ever cost you later. If you cannot argue that a choice is always safe, do not use greedy without testing it against brute force on many small inputs. The coin example shows the danger: greedy looked sensible at each step and was still wrong.

Finally, ask whether the answer is a number you can test. If you can write a yes or no question about a guess, the search style is a good fit. The question needs to be correct, because a wrong question gives a wrong answer with full confidence.

A simple habit helps here. Write the brute force version for small inputs, write the greedy or search version for speed, and run both on the same small inputs. If they disagree, the brute force version is the one to believe, and the faster version has a bug or the wrong idea.

Common mistakes

Beginners make the same few mistakes with these styles. Each one below shows the error or wrong output that comes from it.

Sorting the coins the wrong way for greedy

Greedy must try the largest coin first. If the list is sorted from smallest to largest, the method takes the 1 first and never gets to the bigger coins that would help.

The output is:

[1, 1, 1, 1, 1, 1]

The result is six coins, which is the worst possible answer for this coin set. The code runs without an error message, so the mistake is only visible when you check the answer. This is why a small test case with a known answer is worth writing for every method.

Stopping a brute force search early without checking all branches

A common error in brute force is to return from the first complete answer, without checking the others. The first answer found is not always the best. In the coin example, the first complete way found is 1,1,1,1,1,1 with six coins. The best way, 3,3, is found later. Keep the best answer, and check every branch.

Forgetting the stop condition in the search

The search style needs a limit on the guesses. If the coins cannot make the amount at all, the search above stops because the guess is capped at the amount. Without that limit, the loop would run forever. In Python, a forever loop shows no error message. The program just keeps running until you stop it, so a time limit on the command is the way to notice it.

Trusting a yes or no question that is wrong

If can_pay_with_at_most returns True for an amount that cannot be paid, the search returns a wrong answer. The check is the most important piece of the search style, so test it on small amounts where you know the answer by hand. For the coin set [2, 5] and the amount 9, the answer is 3 coins, because 5 + 2 + 2 is 9, and no two coins make 9.

Practice

Each exercise is followed by its answer. Work the exercise first, then check your answer. For the first two, you can use the script above to check your work.

Exercise 1

Use the coin set [1, 2, 5] and the amount 11. Find the answer that greedy gives. Then decide whether greedy is correct here, by finding the fewest coins with a short argument, not with a list of every possible way.

Show the answer

Greedy takes 5, then 5, then 1. That is [5, 5, 1], which is 3 coins. Greedy is correct here. Two coins cannot make 11, because the largest two coins add up to 10 at most (5 + 5). So 3 is the fewest.

Exercise 2

Use the coin set [1, 3, 4] and the amount 10. Find the answer that greedy gives. Then find the fewest coins by hand. Is greedy correct for this case?

Show the answer

Greedy takes 4, then 4, then 1, then 1, which is [4, 4, 1, 1], a total of 4 coins. The fewest is 3 coins: 4 + 3 + 3 is 10. So greedy is not correct for this case.

Exercise 3

Use the coin set [1, 2] and the amount 3. Write every complete way to pay 3, in the order a brute force method would count them. Then give the fewest number of coins.

Show the answer

The ways are 1,1,1, 1,2 and 2,1. That is 3 complete ways. The fewest is 2 coins, from 1,2 or 2,1.

Exercise 4

Use the coin set [2, 5] and the amount 9. Use the search style. Write the guess for each step, and say what the yes or no check answers for each guess. Give the final answer.

Show the answer

Guess 1: can 9 be paid with at most 1 coin? No, neither 2 nor 5 is 9. Guess 2: can 9 be paid with at most 2 coins? No, the largest two coins give 10 at most, and the choices of two coins are 2 + 2 = 4, 2 + 5 = 7 and 5 + 5 = 10, none of which is 9. Guess 3: can 9 be paid with at most 3 coins? Yes, 5 + 2 + 2 is 9. The answer is 3.

Exercise 5

A volunteer writes a greedy method for the coin set [1, 3, 4], and sorts the coins from smallest to largest instead of largest to smallest. Predict the output for the amount 6, and say what is wrong with the method.

Show the answer

The output is six coins of value 1: [1, 1, 1, 1, 1, 1]. The method takes the smallest coin first, and it never reaches the larger coins that would give a shorter answer. The fix is to sort from largest to smallest with reverse=True.

Summary

• Brute force tries every possible answer and keeps the best one. It is always correct for a finite problem, but it can be very slow.
• Greedy takes the best-looking choice at each step and never goes back. It is fast, but it is correct only for some problems.
• Search the answer guesses an answer, asks a yes or no question about the guess, and stops at the first guess that works.
• The same problem can be solved by all three styles, and the results can differ. Test a fast method against a brute force method on small inputs.
• A test case with a known answer, worked out by hand, catches most of the mistakes in these methods.