Definition 2.1.1.
An algorithm is a finite sequence of instructions for doing a task.
Section 2.1 Definition of an Algorithm
We begin with a formal definition of an algorithm. Then we introduce the instructions that we will use. We end with an algorithm for computing powers of integers. Throughout this section, we give examples of algorithms.
By finite we mean that there is an end to the sequence of instructions.
The joke in Figure 2.1.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:
A recipe is a real-life example of an algorithm. The pancake recipe below uses the same format as our algorithms. It already has some key features.
Our algorithms always have an input. The input contains everything needed to do the task. In the pancake example, the inputs are milk, sugar, flour, eggs, salt, and oil.
The output is what the algorithm produces, or returns, after all instructions have been followed. We list the output of the algorithm after the instruction
return. In our example, the output is pancakes.
The pancake algorithm also has a loop. You
repeat the steps for frying pancakes until there is no batter left.
Algorithm 2.1.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.
Algorithms can use many kinds of instructions, as shown in the recipe above. In this course, our algorithms use only computations with integers. Each algorithm has four parts:
-
The word Algorithm is 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 and by which variable name we refer to them in the algorithm.
-
The Output tells us what the algorithm does by stating how the numbers in the output are related to the numbers in the input.
-
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.
Under input, the pancake recipe gives the amounts of the ingredients and the size of the eggs. We use variables for the input values so we can refer to them in the algorithm. We also describe the output values and their properties.
For very simple algorithms, stating the output and then giving the instructions may seem repetitive. For more complicated algorithms, both parts are needed. Different sequences of instructions can also give the same output.
We use the instructions
let, if-then, repeat-until, and return in our algorithms. We explain each instruction below. We also use standard mathematical notation for computations. An instruction may contain commands and mathematical expressions. Before following the instruction, we first evaluate its mathematical expressions.
We number an algorithm’s instructions and follow them in that order. Each numbered instruction is called a step. A
repeat-until loop changes this order by telling us to repeat earlier instructions. The conditional if-then also changes which commands we follow, depending on whether a statement is true or false.
The video in Figure 2.1.4 reviews the main ideas above. It introduces the instruction
return and gives the first examples of algorithms with numerical input and output.
