2

What is an algorithm?

Posted October 1st, 2010 in Game Design and tagged by Callum Lawson

A algorithm is defined by both the algorithmic problem and its solution. An algorithmic problem is the characterisation of all the legal inputs for the algorithm and the desired outputs for those inputs. This is a rather trivial example of an algorithmic problem:

  • Given a set of numbers (i.e 5,9,7,2,1,5) return how many numbers are divisible by 3.
For the above set of numbers the answer is 1. One could easily write a function that would give this output:

for input(a,b,c,d….) output(1) 


This would provide the correct output for the example set of data but not all possible sets of data – it is not an algorithmic solution. An algorithmic solution is one which will provide the correct output for any legal input. The pseudo-code below would be an example of an algorithmic solution for this problem.

(1) create variable a
(2) for – number of numbers in the set
           if – current number is divisible by 3
           add one to variable a
(3) return a


This code would produce the correct output for this algorithmic problem regardless of what the input is as long as it is a legal input (a set of numbers). It does not matter if the set is 5 numbers or a million – the correct result will be returned.

After claiming that my line of sight code in the previous post was an algorithm I realised that I do not know the definition of one. So I did some research and wrote the above. In hindsight I think I was correct in calling my code an algorithm.

2 Responses so far.

  1. MW says:

    Remember that an algorithm does not have to be mathematical; Darwinian evolution is an algorithm — that is, it explains the way things are in the biological world today via a (fairly simple) "computer program" which posits random variation and then selects those variants which have a statistically better chance of reaching reproductive age than others . . .

    (Question being, of course: who wrote the program? Answers on a postcard please.)

    Martin Woodhouse

  2. A more elegant algorithm for determining whether a given decimal number is divisible by three (you’ll recall) is:

    A: add up its digits.
    B: repeat A upon the result until the sum obtained is single-digit.
    C: if this sum is divisible by three with no remainder then the same is true of the original number: otherwise it is not.

    Question: Why is this the case?

    That is : why does this algorithm work?

    There’s an algorithm comparable is general form for divisibility by five, isn’t there? Is it also the case for seven? For any other prime number? For ‘divisibility without remainder’ by any prime number, in general?

    Make your own contribution to number theory, guys.

    With cheers and best wishes,

    Martin

Leave a Reply