Introduction to Algorithms

General Algorithm History

Algorithms were used to solve every day problems long before computers were

ever invented. In fact algorithms have been used for so long they were named for the ninth

century mathematician, Al-Khowarizmi. Algorithms have been used for centuries to solve the

most complex problems that humanity has encountered. One of the most famous algorithms

was imagined in ancient greece. Euclid's algorithm for calculating the greatest common divisor

of two integers had and still does have impacts in the mathematical world. The importance of

algorithms in today's society should not be underestimated. The computer, for example, would

have no purpose since almost all programs are written using an algorithmic approach.

Algorithm Defintions and General Concepts

Webopedia defines an algorithm as:

"A formula or set of steps for solving a particular problem. To be an algorithm, a set of
rules must be unambiguous and have a clear stopping point. Algorithms can be expressed
in any language, from natural languages like English or French to programming languages
like FORTRAN.

We use algorithms every day. For example, a recipe for baking a cake is an algorithm.
Most programs, with the exception of some artificial intelligence applications, consist of
algorithms. Inventing elegant algorithms -- algorithms that are simple and require the fewest
steps possible -- is one of the principal challenges in programming."

Pseudo Code

Pseudo Code is used to represent algorithms in a programming language free context. It is basically a language that is not implemented on a computer. These are the constructs of pseudo code.

variable <-- value

- This means that variable is assigned value.

if (condition) then
statements1
else
statements2

- This is used for making choices in pseudo code. if some condition is true then statements1 is done. if condition is false then statements2 are done.

while {condition} do
statement

-This is used for repeating statements in pseudo code. As condition evaluates to true the statements are done.

repeat until {condition}
statement

- Statements are evaluated until the condition evaluates to statement true, then exit the loop.

for {condition} do
statement

- Evaluates statement as long as condition is true.

Plain English can be used in pseudo code as long as the point is made clear. Math operators can also be used, for example <, >, <, >, and not equals.

Here is an example for an algorithm that will assign the variable x the numbers from 1 to 10 except for 5.

x <-- 0

while x <>
if x = 4 then
x <-- x + 2
else
x <-- x + 1

This is done very simply. x is initialized to 0. The algorithm enters the while loop because 0 <>