What is an algorithm?

Some definitions first

One of the goto resources for expert-level mathematicians and engineers is Wolfram MathWorld. The definition reads as follows:

An algorithm is a specific set of instructions for carrying out a procedure or solving a problem, usually with the requirement that the procedure terminate at some point. (…)

Wolfram MathWorld

A more mainstream resource, the Merriam-Webster, states the following:

(An algorithm is) a procedure for solving a mathematical problem (…) in a finite number of steps that frequently involves repetition of an operation.

broadly: a step-by-step procedure for solving a problem or accomplishing some end

Merriam-Webster

Curiously the more math-heavy site is not specifically mentioning any mathematics. Indeed the deeper philosophical understanding of an algorithm goes beyond the mathematical.

The word Algorithm comes from the Latinization of Al-Khwārizmī, the last name of Persian mathematician and astronomer Muḥammad ibn Mūsā al-Khwārizmī.

Here are the key points of an algorithm:

There is a task we want to solve
Each instruction is unambiguous
There is a finite set of instructions to accomplish the above
After completion of the set of instructions, we get a result

Let’s unpack the above.

  • A task could be:
    • getting from A to B (on a map or physically)
    • baking a cake
    • finding a word in a dictionary
    • computing approximations of π (Pi)
    • identifying a human face based on a large image data-set
    • determine shopping behavior of previous customers
    • winning at chess

Even from this list, you can see a difference in complexity. Another important part of an algorithm is the finiteness of its instructions.

  • An algorithm cannot have infinite number of instructions.

Lastly, after the algorithm terminates, we need a result or an output. Here are three from the earlier list of tasks:

  • travel instructions result in arriving at our destination
  • a recipe results in a dish, cake, or dessert
  • computing π will result in a set of decimal digits approximating π

The relevance of algorithms in everyday life

From the previous examples, you might guess that many aspects of everyday life could be classified as algorithms. Many are automated and seemingly insignificant—tying your shoes, filling a cup with liquid, opening a door, and many more.

With more experience and knowledge, you can apply algorithms to other parts in life. Brian Christian and Tom Griffiths cover many in their book Algorithms to Live By: The Computer Science of Human Decisions, e.g., finding a parking spot, organizing one’s inbox, or determining the balance of trying new restaurants vs. revisiting favorite ones.

Algorithms and computers

When computers come into play, we have to understand a few technical details first. A computer is a deterministic machine, which means that it will always run in a pre-defined way. It is, by definition, impossible to generate truly random numbers with a “regular” computer.

Computers run on binary numbers (that is a string of 0s and 1s). There is always a data input and a data output. Both can only be in the form of binary numbers. We will go into more detail in later classes to understand how numbers, text, and other multimedia types can be generated.

Using an algorithm to manipulate data input to generate a data output is called a computation.