Properties of a valid algorithm

First, an acknowledgement to Prof. Wayne Brown from the University of Arizona whose well written lesson Introduction to Algorithmic Thinking forms a significant basis of the statements made here, including verbatim phrases.

An algorithm is an ordered step-by-step sequence of statements or instructions that, if followed, finds a solution to a problem. For an algorithm to be useful, it must satisfy the following properties:

  • The statements or instructions must be executable; meaning that it must be possible for the computer to follow through on the instructions given without any extra information.
  • The statements or instructions must be unambiguous; meaning that every human computer will be able to follow the statements or instruction in the same way.

Some algorithms are quite straight-forward; for example, a recipe is an algorithm for creating a meal. If the steps are followed through step-by-step and the statements or instructions are clear and unambiguous, every person using that recipe should produce the same result.

  1. Combine 1.5 cups of all-purpose flower, 3.5 teaspoons of baking powder, 1 teaspoon of salt and 1 tablespoon of white sugar in a large bowl and thoroughly mix the two.
  2. Make a depression in the center of the combined powders.
  3. Separate the egg white of 2 eggs from the yokes and set the egg white aside in a second large bowl. Put the egg yokes into the depression.
  4. Place 3.0 tablespoons of butter in a bowl and place in the microwave until the butter is melted. Pour the melted butter into the depression.
  5. Pour 1.25 cups of milk into the depression.
  6. Using a whisk, mix the ingredients until the viscous batter is smooth, meaning when disturbed or moved, the batter returns to a smooth surface.
  7. Whip the egg whites vigorously with a whisk until it forms a foam that does not collapse under its own weight to form a smooth surface.
  8. Fold the whipped egg whites into the batter.
  9. Heat a waffle iron.
  10. Pour the resulting batter into a waffle iron.
  11. Allow the waffles to continue baking until no more moisture escapes in the form of steam, then remove them from the waffle iron.
  12. If there is more batter left over, return to Step 9.

Are these valid instructions? For the most part, probably yes, except for Step 8. While the average chef may know what folding is, the average person may not. This would require additional information beyond the recipe

You may note that the above instructions are also otherwise very verbose. Most recipes use an abbreviated language under the assumption that the reader understands what is to be done (for example, it is assumed the reader knows what folding is, understands that whipping is performed with a whisk, and has the common sense to continue making waffles until the batter is finished).

Other statements or instructions in a recipe that may cause problems are ambiguous amounts or ambiguous materials:

  • A dash of salt.
  • 0.5 cups of oil.

In the first case, ten chefs are likely to end up with different quantities of salt so as to make up a dash. The second, olive oil and hazelnut oil have very different tastes from canola oil. The resulting meal will taste different.

Some statements may be conditional:

  • If you have 30% whipping cream, add 10 mL of cream and 10 mL of water into the bowl,
    otherwise, if you have 18% table cream, add 20 mL into the bowl,
    otherwise, if you have 10% half-and-half cream, add 30 mL into the bowl,
    otherwise, add 40 mL of milk into the bowl.
  • If you a stronger spicy heat, include half a ghost pepper into the bowl.

This allows the chef to alter the recipe based on the current circumstances.