Monthly Archives: Jan 2023

The Algorithm

--- algorithm (noun) ---
A well-defined procedure consisting of a finite number of consecutive steps. Often confused with its realization (implementation).


--- The Algorithm (proper noun) ---
A musical project that blends electronic music with progressive metal. Often confused with random noises.


--- algorithm (example) ---
def is_alive()
    return flip_coin()

def life()
    while(is_alive())
        go_outside();
        take_pictures();
        persist();
    decay();

Aren’t algorithms fascinating? Well-defined procedures that solve well-defined problems – often with the goal to find the most efficient solution. It’s the single most important thing that amazes me in computer science.

My most favorite problem in algorithmics is one of the most simple ones. Suppose you have a short word, let’s call it T. Additionally, a long text S is given. The task is to determine whether the word T is contained within the text S. Thus, we want an algorithm for a simple search! Suppose the word T contains n distinct characters; for example T = “alive” has a length of n = 5. Similarly, the text S has a length of m, for example, S = “The tree is alive.” has a length of m = 18 (including the spaces and the period).

The most simplest algorithm aligns T at the first position of S and compares all n characters of T to the first n characters of S, which requires n comparisons (in other words, for our above example we answer the question whether “alive” and the first five characters of S are identical. Hint: they are not). Afterwards, the word is shifted to the next position of S and the comparison is repeated. This happens for all m starting characters of S. The problem? This will take a total of m times n comparisons which already amounts to 90 comparisons for our little toy example.

But what other solution could there be? There are many. None of them are easy to understand (at least for me), but all are fascinating. The first one I learned was the KMP algorithm, which performs mind-boggling reuses of previously obtained information about differing characters. The fascinating part: It only needs (roughly) m + n comparisons! A speed-up that determines whether we are able to browse the internet or not, whether we can perform research on molecular data or not, and whether we can advance as a technological species or not. Algorithmic design makes or brakes today’s society (at least for now, until climate change kicks in – always end on a positive note, right?).