Definition 2.1.
An algorithm is a finite sequence of instructions for performing a task.
Section 2.1 Definition of an Algorithm
We give a formal definition of an algorithm, introduce the instructions that we will use, and end with an algorithm for computing powers of integers. Throughout this section we will give examples of algorithms.
By finite we mean that there is an end to the sequence of instructions. The joke in Figure 2.2 refers to a misunderstood sequence of instructions with no end.
Question: Why did the programmer go into the shower to wash his hair and never come out?
Answer: He read the instructions on the shampoo bottle: Massage into wet hair. Lather. Rinse. Repeat.
A recipe is a real-life example of an algorithm. The pancake recipe below is in the same format that we use to present algorithms. It already has some of the key features. Our algorithms always have an input, which contains all the ingredients needed to perform the task. In the pancake example we assume that kitchen hardware such as bowls and spoons are available, and we do not list them as input. The output is what the algorithm produces, or returns, when all instructions have been followed. We list the product of the algorithm after the instruction return. The pancake algorithm also contains a loop. You are instructed to repeat frying pancakes until there is no batter left.
Algorithm 2.3. Eierkuchen.
- Input:
- 1 cup of milk, 2 tablespoons of sugar, 1 cup of flour, 3 large eggs, 1 pinch of salt, and oil for the pan
- Output:
- a stack of pancakes on a plate
- Mix flour, eggs, sugar, and salt with an egg beater until the mixture is homogeneous.
- Slowly add the milk while stirring the mixture.
- Heat a pan with oil.
- repeatthe following steps:
- Take a ladle of batter and pour into the pan.
- Fry pancake on one side.
- Flip pancake.
- Fry pancake on other side.
- Take pancake out of the pan.
- Put pancake onto plate.
- untilbowl is empty.
- returnplate with pancakes.
Although algorithms can consist of any kind of instructions (as illustrated in the recipe above), the algorithms in this course will be limited to computations with integers. Our formulation of algorithms consist of four parts:
- The word Algorithm is usually followed by a name that we can use to refer to the algorithm.
- The Input specifies what kind of numbers can be given to the algorithm. We often give the properties we expect them to have for the algorithm to work. We also include the variable names that are used to refer to these numbers.
- The Output tells us what the algorithm does by stating the properties of the numbers that the output of the algorithm.
- A sequence of instructions that yields the output. This sequence of instructions describes how the output is generated. We number the instructions and follow them in their numerical order.
In the pancake recipe under input we give the amounts of the ingredients and the size of the eggs. We formulate the input values as variables, so that we can refer to them in the algorithm. We also specify the output values and their properties.
For very simple algorithms declaring the output and giving the sequence of instructions will seem redundant. For slightly more complicated algorithms this is not the case. You will also see that there are different sequences of instructions that yield the same output.
In the formulation of algorithms we use the instructions let, if_then, repeat_until, and return, which we explain in detail in the following. In addition we use standard mathematical notation for computations. Each instruction in an algorithm consists of commands and mathematical expressions. Before we follow any specific instruction we always evaluate any mathematical expression first.
We number the instructions in the algorithms and follow the instructions in this order. Each numbered instruction is called a step. The repeat_until loop can be used to change this order by telling us to repeat previous instructions. The conditional if_then also changes which commands are to be followed, depending on whether a statement is true of false.
In the video in Figure 2.4 we recall the main points of the discussion above, introduce the instruction return and give first examples of algorithms with numerical input and output.
