Sunday, January 11, 2009

My favorite algorithm

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?


Anonymous said...

Um this is a crazy irrelevant comment.. I just came across this blog searching for NUS SoC grad admissions info... are you - is anyone on this blog - familiar with the research program interview process? I can't find any info and have no clue how to prepare! My interview's in 2 days!

Melvin said...

Research program interview? I don't remember such an interview when I applied for graduate school. I suppose times have changed.

You probably want to have some idea of the kind of research work you would like to do (systems/theory) and be able to convince the panel that you have the ability to do it.

Anonymous said...

ah well.. just had the interview :) yep they mainly just asked my previous research work and what i want to do..