Introduction to algorithms
From Wikiversity
Contents |
[edit] Introduction
See also Algorithm on Wikipedia
[edit] Everyday Example
Here is a perhaps slightly whimsical example of an algorithm.
Algorithm for making 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.
As can be seen, the algorithm is a set of steps that can be followed in order to acheive a result.
[edit] Subprocedures
Algorithms are often broken down into smaller chunks called or subprocedures. This is both so that they are easier to read, and also because then parts of the algorithm can be reused. What follows is the above algorithm in a more formal manner. The text in italics below are the names of the subprocedures that are being called.
Algorithm for making toast (2.0)
get a loaf of bread. cut slice from the loaf of bread. move the slice of bread to the toaster. turn on the toaster. wait for the toaster to finish. move the slice of toast to a plate. spread the slice of toast with butter.
[edit] Variables
In the above example it is fairly simple to follow the piece of toast through the algorithm, but if you imagine that the algorithm could become more complex, and thus the progress of the toast much harder to follow. In order that, at any point in the algorithm, it is clear what is being talked about, names are often given to things. For example
Algorithm for making toast (3.0)
LET A = a loaf of bread LET T = a toaster LET P = a plate LET B = some butter LET S = cut slice from A move S to T turn on T wait for T move S to P spread S with B
[edit] Flow Control
Our current toast making algorithm works well if you are making toast for yourself, but what if you have a few friends round for breakfast and you need to make them toast as well? The algorithm clearly needs to be improved so that we can make toast for everyone. Also, simply waiting for the toasted is very boring, we could be doing something else while we wait. The third problem with making toast for friends is that they are fussy, what if some of them want butter whilest others prefer margarine, or even just plain toast
Algorithm for making toast (4.0)
LET A = a loaf of bread
LET T = a toaster
LET P = a plate
LET B = some butter
LET M = some margarine
FOR every friend (F) eating toast{
LET S = cut slice from A
move S to T
turn on T
WHILE T is not finished{
talk to F
}
move S to P
IF F likes B{
LET X = B
}ELSEIF F likes M{
LET X = M
}ELSE{
LET X = NOTHING
}
spread S with X
move P to F
}
As can be seen, to resolve the three problems above, I had to implement the three main types of flow control, a For Loop, a While Loop and an If Statement. It should be obvious from the example what each of these does. I also involved a new variable X, which unlike the variables I have used before changes its value as the algorithm progresses.
[edit] Basic concepts
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 fundemental 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 certains condition 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!
- Subprocedures. 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.
[edit] Algorithms commonly studied
Many algorithms are currently under intense study for various reasons. They include:
- Sorting algorithms. A sorting algorithm will take a set of objects and arrange the objects in ascending (or descending) order. While this is a simple problem and there are many existing algorithms to tackle this problem efficiently, new algorithms (and problems with older ones) are published all the time.
- Artificial Intelligence. AI algorithms typically accept an input representing its environment (eg. a chess board) and try to find some legal move to respond favourably to the environment or an opponent (eg. calculating a good chess move). Today modern chess AIs can beat even professionals and regularly challenge world grandmasters to intense, decisive matches. Still, some simple board games (like Japanese Go) remain impervious to attack. AI has also been recently employed in anti-fraud software and email spam filters.
- Numerical Computation. More and more mathematicians and computer scientists are using computers to do research, eg. to collect data, test new theories or process experimental results. Some researchers have even tried to use computers to prove theorems! (A proof to the four-color theorem was, controversially, completely produced by computer.) Ever faster algorithms need to be invented to cope with this massive increase in demand.
