Definition of Algorithm
edit
Merriam-Webster Online defines "Algorithm" as " a step-by-step procedure for solving a problem or accomplishing some end, especially by a computer" [1]. The dictionary definition is missing the component that the procedure must be finite, that is, there has to be a condition for the termination of the algorithm.
Examples:
1. One example would be knitting socks.
The first step is to cast on stitches. Step-by-step the rows are knitted, the heel turned, and finally the last row cast off. The algorithm specifies how to do the sock, but each sock knitted is different, as it uses different wool, but all are similar in structure to each other.
2. Another important example would be sorting a hand of cards.
There are multiple ways of doing this, but one method is to take the lowest card and move it to the leftmost (or rightmost) position. Next, find the second lowest card and move it to the second leftmost position. Repeat until the cards are sorted.
Everyday example:
Here are perhaps slightly whimsical examples of an algorithm.
Algorithm for making buttered toast (1.0)
|
- Get a loaf of bread.
- Cut one slice from end of the loaf of bread.
- Put slice of bread into toaster.
- Turn toaster on.
- Wait for toaster to finish.
- Put toasted bread onto a plate.
- Spread butter on toast.
|
Brushing teeth
|
- grab tooth paste
- take off the lid
- grab tooth brush
- put a dab of tooth paste onto the tooth brush
- put lid back onto tooth paste
- turn on the sink
- wet the tooth brush
- turn off the sink
- brush all tooth surfaces consistently with circular motion
- when complete, turn on sink
- fill a small cup with water
- turn off sink
- rinse mouth
- spit into sink
- turn on sink
- rinse tooth brush and sink
- turn off sink
- put toothbrush and tooth paste away
- throw away disposable cup
- shut all drawers/cabinets
|
As can be seen, the algorithm is a set of steps that can be followed in order to achieve a result.
This simple example already contains many components commonly found in most algorithms:
- Instructions. Instructions are the heart and soul of any algorithm. An algorithm will consist of a series of sub-algorithms, each performing a smaller task. Extracting individual digits from the numbers to be added may well be an entire task in itself. Some instructions, like digit addition, can be considered fundamental instructions which cannot be broken up further; all algorithms can eventually be broken down into these instructions, like objects being composed of atoms.
- Variables. temporary and carry are both temporary values used to store additional information the algorithm needs to function correctly or effectively. Their values can vary as the algorithm progresses, hence their name.
- Conditionals. Some algorithms may need to make a decision somewhere in it. If the sum of the current two digits is 10 or larger, 1 will be carried over to the next digit position, otherwise nothing (ie. zero) is carried. Conditionals allow an algorithm to selectively execute instructions based on certain conditions which must be satisfied.
- Looping. The for each...end for instruction means to run certain instructions for each object in a set, in this case for each digit in a number. This is a special case of looping, the act of repeating a set of instructions while (or until) a goal is reached or a condition is satisfied; in this case while there are digits left (or until there are no digits left). Loops can contain any other instructions, including other loops!
- Subalgorithm. An algorithm may not be able to do all the work on its own. Usually, a large, complex algorithm can be broken up into parts, each perfoming a specific task. Smaller algorithms are easier to reuse, for example the for each ... digit selection algorithm could be reused in subraction, multiplication and division algorithms, and so on. Breaking up algorithms into logical parts also make it easier to analyze their behaviours and properties from a mathematical point of view.
- Performance. While initial algorithms may seem to function, you may discover that they may not be the best choice in the long term. For example, a simple bubble sort may work for a small amount of items, but if you try it on a large amount of data, it will take a massive amount of time. An algorithm with better performance would include the Merge Sort.
|
