My favorite algorithm

date: 2009-12-23 18:04:53 +08:00 category: cs

This post originally appeared here on 11/01/09. This is the last in a series of reposts from the NUS SoC blog.

Many of the mechanical procedures we learned in primary and secondary school for calculating the result of certain mathematical operations are really just numerical algorithms. Usually we start with the Addition algorithm for finding the sum of two numbers, this is typically followed by the Multiplication algorithm, which uses the Addition algorithm and digit shifting. Often we are just taught the steps, but not the reason why following them will give us the correct answer (correctness) or how the steps were developed in the first place (design).

The problem posted by Chris Henry on the frequency of the mode reminded me of a similar problem, that of finding the majority in a collection of $n$ items. The majority is the item whose frequency is more than $n/2$. This problem has a very clever but simple solution that only needs only one pass over the data. It was listed by one of its inventors, J Stother Moore, as one of his best ideas. It is also my favorite algorithm.

What is your favorite algorithm?