An algorithm specifies a series of steps that perform a particular computation or task. Algorithms were originally born as part of mathematics – the word “algorithm” comes from the Arabic writer Muḥammad ibn Mūsā al-Khwārizmī, – but currently the word is strongly associated with computer science. Throughout this book we’ll examine a number of different algorithms to perform a variety of tasks.
Algorithms resemble recipes. Recipes tell you how to accomplish a task by performing a number of steps. For example, to bake a cake the steps are: preheat the oven; mix flour, sugar, and eggs throughly; pour into a baking pan; and so forth.
However, “algorithm” is a technical term with a more specific meaning than “recipe”, and calling something an algorithm means that the following properties are all true:
Studying algorithms is a fundamental part of computer science. There are several different characteristics of an algorithm that are useful to know:
Most of these questions will be discussed for the algorithms covered in this book.
Let’s look at a very simple algorithm called find_max().
Problem: Given a list of positive numbers, return the largest number on the list.
Inputs: A list L of positive numbers. This list must contain at least one number. (Asking for the largest number in a list of no numbers is not a meaningful question.)
Outputs: A number n, which will be the largest number of the list.
An implementation in Python:
def find_max (L): max = 0 for x in L: if x > max: max = x return max
Does this meet the criteria for being an algorithm?
There can be many different algorithms for solving the same problem. Here’s an alternative algorithm for find_max():
def find_max (L): if len(L) == 1: return L v1 = L v2 = find_max(L[1:]) if v1 > v2: return v1 else: return v2
Let’s ask our questions again.
Is it unambiguous? Yes. Each step is simple and easily translated into Python.
Does it have defined inputs and outputs? Yes.
Is it guaranteed to terminate? Yes. The algorithm obviously terminates if L is of length 1. If L has more than one element, find_max() is called with a list that’s one element shorter and the result is used in a computation.
Does the nested call to find_max() always terminate? Yes. Each time, find_max() is called with a list that’s shorter by one element, so eventually the list will be of length 1 and the nested calls will end.
Finally, does it produce the correct result? Yes. Here’s a sketch of a proof. 
Consider a list of length 1. In this case the largest number is also the only number on the list. find_max() returns this number, so it’s correct for lists of length 1.
Now consider a longer list of length N+1, where N is some arbitrary length. Let’s assume that we’ve proven that find_max() is correct for all lists of length N. The value of v2 will therefore be the largest value in the rest of the list. There are two cases to worry about.
With these two cases, we’ve now shown that if find_max() is correct for lists of length N, it’s also correct for lists of length N+1. In the first part of our argument, we’ve shown that find_max() is correct for lists of length 1. Therefore, it’s also correct for lists that are 2 elements long, and 3 elements, and 4, 5, 6, ... up to any number.
This may seem like a trick; we showed that it’s correct for the trivial case of the single-element list, and then showed that it’s correct on a problem of a certain size. Such proofs are called inductive proofs, and they’re a well-known mathematical technique for proving a theorem.
Carrying out an inductive proof of some property requires two steps.
Once you have both demonstrations, you’ve proven the property is true for an infinite number of values of N; correctness for N=1 implies that the N=2 case is also correct, which in turn implies correctness for N=3, 4, 5, and every other positive integer. Not every theorem can be put into a form where an inductive proof can be used.
XXX something on induction
|||There are special situations where algorithms that are sometimes wrong can still be useful. A good example is testing whether a number is prime. There’s an algorithm called the Rabin-Miller test that’s always correct when it reports a number is composite, but has a 25% chance of being wrong when it reports a number is prime. One test therefore isn’t enough to conclude you’ve found a prime, but you can perform repeated tests and reduce the chance of being wrong to as low as you like (but never zero).|
|||It’s possible to write formal proofs of correctness for an algorithm, but the resulting proofs are lengthy even for short algorithms such as this one.|