Algorithms: What’s the problem?

yourbasic.org

A good programmer describes algorithms in a form that can be efficiently executed by machines and easily understood by humans.

Algorithms and programs are pretty much the same thing – the main difference is that we can talk about algorithms without relying on a programming language. An algorithm invented today will be equally as useful when the last Java programmer has logged out. Here is an attempt at a formal definition.

An algorithm is a stepwise procedure of well-defined executable instructions intended to perform a task or solve a problem, often with the added requirement that the procedure must come to a stop.

A programmer’s job is to design and implement algorithms that are correct, clear and efficient.

Problems

Algorithms are commonly used to solve certain types of computational problems. We can often describe such a problem by specifying a relationship between input and output.

The sorting problem, for example, can be described like this:

Input: a sequence a₁, a₂, ..., a_n of n numbers.
Output: a permutation (reordering) a'₁, a'₂, ..., a'_n of the input, which satisfies the property a'₁ ≤ a'₂ ≤ ... ≤ a'_n.

As an example: given the input sequence 12, 24, 13, 12, 8 a sorting algorithm must produce the output sequence 8, 12, 12, 13, 24. One such specific example of input for a problem is called an instance of the problem.

We say that an algorithm is correct if the algorithmic procedure stops for each problem instance and returns the required output. The algorithm solves the problem.

Pseudocode

When talking and writing about algorithms it’s convenient to use pseudocode instead of executable code.

Pseudocode is a compact and informal high-level description of an algorithm intended for humans rather than machines.

In pseudocode you can omit details that are easy to figure out for a human, such as variable declarations and system-specific function calls. You can also use natural language and mathematical notation.

For obvious reasons, there is no standard for writing pseudocode, but here is a typical example. First take a look at the code written in Go.

// Sum returns the sum 1 + 2 + ... + n, where n ≥ 1.
func Sum(n int) int {
    var sum int
    for i := 1; i <= n; i++ {
        sum += i
    }
    return sum
}

The same algorithm described in pseudocode might look like this.

// Returns the sum 1 + 2 + ... + n, where n ≥ 1.
Algorithm sum(n)
    sum ← 0
    for i ← 1 to n
        sum += i
    return sum

Efficiency

Different algorithms that solve the same problem can have large performance differences. Here is a typical situation.

The number of machine instructions required to sort n numbers with Insertion sort can be approximated with the formula c₁n², where c₁ is a constant that depends on how well the algorithm is implemented.
Quicksort requires roughly c₂n log₂ n instructions, where c₂ is an implementation-dependent constant.

From this we can see that Quicksort is much faster than Insertion sort when n is large. This holds true even if we use an incompetent implementation of Quicksort running on a slow computer.

Example

The differences become painfully obvious when we plug in some actual values in the formulas.

Let's run Insertion sort on a fast computer that can execute 10⁹ instructions per second. The algorithm is implemented by a skillful programmer and the constant c₁ = 5.
Quicksort run will run on a much slower computer that can only execute 10⁷ instructions per second. Also, the implementation is sloppy: c₂ = 100.

For small instances of the sorting problem, the faster computer wins.