Basic Concepts of Computer Programming

"Practice yourself, for heaven's sake, in little things; and thence proceed to greater." , Epictetus, Discourses IV.i (c. A.D. 110)

The notion of an algorithm is basic to all of computer programming. Before we write a single line of code, we need to understand what an algorithm actually is, and what distinguishes a rigorous algorithm from an informal set of instructions.

This post explores the foundational concepts that every programmer should know, drawn from the timeless principles in Donald Knuth's The Art of Computer Programming.

What is an Algorithm?

The word "algorithm" has a fascinating history. It comes from the name of a Persian mathematician, al-Khwārizmī (c. 825 CE), who wrote influential texts on arithmetic and algebra. The word evolved through centuries of use, eventually settling into its modern form.

But what is an algorithm? It's similar to a recipe, process, method, or procedure, but with crucial differences.

An algorithm must satisfy five essential properties:

1. Finiteness: It must terminate after a finite number of steps
2. Definiteness: Each step must be precisely defined
3. Input: Zero or more inputs from specified sets
4. Output: One or more outputs related to the inputs
5. Effectiveness: Operations must be basic enough to do exactly

These properties distinguish algorithms from vague instructions like "cook until done" or infinite loops that never terminate.

The Assignment Operation

Before we look at our first algorithm, we need to understand a fundamental operation: assignment.

In algorithms, we use the arrow notation ← for assignment. When we write:

n ← n + 1

This means "replace the value of n with n plus 1." The arrow distinguishes assignment from equality testing. We don't say "n = n + 1" (which would be mathematically false), we say "n gets n + 1."

Crucially, the order of assignments matters. When executing multiple assignments, the sequence can completely change the result.

This is why Euclid's algorithm uses m ← n, n ← r in that specific order, reversing it would lose the original value of n before we could save it.

Euclid's Algorithm

Now we're ready for our first complete algorithm: Euclid's algorithm for finding the greatest common divisor (GCD) of two positive integers.

This algorithm is over 2,300 years old, appearing in Euclid's Elements (Book 7). Despite its age, it remains one of the most efficient methods for computing GCDs.

Algorithm E (Euclid's algorithm). Given two positive integers m and n, find their greatest common divisor.

• E1. [Find remainder.] Divide m by n and let r be the remainder.
• E2. [Is it zero?] If r = 0, the algorithm terminates; n is the answer.
• E3. [Reduce.] Set m ← n, n ← r, and go back to step E1.

Let's trace through this algorithm step by step:

Try different values to see how the algorithm works. Notice that it always terminates, this is the finiteness property in action.

Why Does Euclid's Algorithm Work?

The key insight is a mathematical property: gcd(m, n) = gcd(n, r).

When we divide m by n to get remainder r, the common divisors of m and n are exactly the same as the common divisors of n and r. This means we can keep reducing the problem until r becomes 0.

Since r is always less than n, and n becomes r in each iteration, the values are strictly decreasing. A decreasing sequence of positive integers must eventually reach zero, guaranteeing termination.

Extended Euclid's Algorithm

There's a more powerful version of Euclid's algorithm that not only finds the GCD, but also finds integers a and b such that:

am + bn = gcd(m, n)

This is incredibly useful in cryptography (for computing modular inverses) and number theory.

The algorithm maintains additional variables a, a', b, b' that track the linear combinations as we go. At the end, we can verify that the coefficients actually work.

Mathematical Induction

How do we prove that an algorithm always works? How do we prove mathematical statements about all positive integers?

The answer is mathematical induction, a proof technique that mirrors the structure of algorithms themselves.

Induction has two parts:

1. Base case: Prove P(1) is true
2. Inductive step: Prove that if P(k) is true, then P(k+1) is also true

Like dominos falling, once P(1) falls, it knocks over P(2), which knocks over P(3), and so on forever.

A Visual Example

Consider the beautiful fact that the sum of the first n odd numbers equals n²:

1 = 1²
1 + 3 = 4 = 2²
1 + 3 + 5 = 9 = 3²
1 + 3 + 5 + 7 = 16 = 4²

We can prove this by induction, but there's also a gorgeous geometric proof:

Each new odd number forms an L-shaped piece that extends the square by one row and one column. The L-shape has (n-1) cells on the bottom, (n-1) cells on the right, plus 1 corner cell = 2n-1 cells.

Analyzing Algorithms

Once we have an algorithm, a natural question is: how efficient is it?

For Euclid's algorithm, we can ask: on average, how many times is step E1 executed?

Let T_n be the average number of times E1 is executed when we know n but let m range over all values from 1 to n.

Remarkably, T_n grows logarithmically with n. Specifically:

T_n ≈ (12 ln 2 / π²) ln n ≈ 0.8427 ln n

This means Euclid's algorithm is incredibly efficient, even for very large numbers, it takes only a handful of steps.

What You Now Know

Algorithms have five essential properties. Finiteness, definiteness, input, output, and effectiveness distinguish rigorous algorithms from informal procedures.

Assignment order matters. The sequence m ← n, n ← r is fundamentally different from n ← r, m ← n.

Euclid's algorithm is elegant and efficient. It finds the GCD in O(log n) steps, a result that was proved centuries after Euclid wrote it.

Mathematical induction proves infinite statements. By proving P(1) and P(k) → P(k+1), we prove P(n) for all positive integers.

Algorithm analysis reveals performance. Understanding how efficient an algorithm is matters as much as knowing that it works.

These foundational concepts, algorithms, assignment, termination, correctness, and analysis, form the bedrock upon which all of computer programming is built.