DAA 01: Introduction to Algorithm

INTRODUCTION TO ALGORITHM

History of Algorithm

• The word algorithm comes from the name of a Persian author, Muhammad ibn Musa al-Khwarizmi (c. 825 A.D.), who wrote a textbook on mathematics.

• He is credited with providing the step-by-step rules for adding, subtracting, multiplying, and dividing ordinary decimal numbers.

• When written in Latin, the name became Algorismus, from which the algorithm is but a small step

• This word has taken on a special significance in computer science, where “algorithm” has come to refer to a method that can be used by a computer for the solution of a problem

• Between 400 and 300 B.C., the great Greek mathematician Euclid invented an algorithm

• Finding the greatest common divisor (gcd) of two positive integers.

• The gcd of X and Y is the largest integer that exactly divides both X and Y.

• Ex. the gcd of 80 and 32 is 16.

• The Euclidian algorithm, as it is called, is considered to be the first non-trivial algorithm ever devised.