What is an Algorithm?

Date: 10/21/2001 at 22:30:52
From: jonathan
Subject: Algorithm

My teacher wants us to define and explain, including an example, what 
an algorithm is. I'm having trouble figuring out what one is exactly. 
Can you help? 

Thanks.

Date: 10/22/2001 at 13:34:02
From: Doctor Ian
Subject: Re: Algorithm

Hi Jonathan,

An algorithm is a sequence of instructions that, if followed, is 
guaranteed to reach some goal (or establish for certain that the goal 
is unreachable). The guarantee is important - it's what distinguishes 
an algorithm from a heuristic ('rule of thumb').

You can find several examples of mathematical algorithms here:

   Is Math a Science?
   http://mathforum.org/dr.math/problems/rouzier.03.18.01.html   

But sometimes the concept is easier to understand in terms of everyday 
goals and methods.  

For example, when you've misplaced something, the normal thing to do 
is to try to think of where you might have left it, by using various 
heuristics: Look in the last place you remember having it, check your 
pockets, check your backpack, look on the dining room table, ask your 
mom, etc. Sometimes these work, and sometimes they don't. 

When heuristics fail, you can resort to an algorithm, i.e., 

  For each room in the house,
    For each item in the room,
      Pick up the item.
      If it's the item you're looking for, 
        Terminate the search. 

Note that this will either find the item, or (if you run out of items 
and rooms to check) will establish for certain that it isn't in the 
house.  

Another important feature of an algorithm is that each step has to be 
both unambiguous and implementable.  

Perhaps you've heard the old joke:  

  Q: How do you get four elephants into a Volkswagen?  
  A: Put two in the front seat, and two in the back!  

This isn't an algorithm, because although the steps are unamibiguous, 
they aren't implementable.

Or consider this 'algorithm' for being elected President of the 
United States:

  1. Declare your candidacy.
  2. Campaign.
  3. Get more votes than the other candidates. 

Each of these steps is clearly implementable (someone implements 
them every four years), but some of them are ambiguous. How do you 
'campaign'? How do you 'get votes'? Those steps need to be fleshed 
out a little!

Does this help?  

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/