Page 213 - Discrete Mathematics and Its Applications

192 3 / Algorithms

The term algorithm is a corruption of the name al-Khowarizmi, a mathematician of the ninth
century, whose book on Hindu numerals is the basis of modern decimal notation. Originally,
the word algorism was used for the rules for performing arithmetic using decimal notation.
Algorism evolved into the word algorithm by the eighteenth century. With the growing interest
in computing machines, the concept of an algorithm was given a more general meaning, to
include all definite procedures for solving problems, not just the procedures for performing
arithmetic. (We will discuss algorithms for performing arithmetic with integers in Chapter 4.)
In this book, we will discuss algorithms that solve a wide variety of problems. In this
section we will use the problem of finding the largest integer in a finite sequence of integers to
illustrate the concept of an algorithm and the properties algorithms have. Also, we will describe
algorithms for locating a particular element in a finite set. In subsequent sections, procedures
for finding the greatest common divisor of two integers, for finding the shortest path between
two points in a network, for multiplying matrices, and so on, will be discussed.

EXAMPLE 1 Describe an algorithm for finding the maximum (largest) value in a finite sequence of integers.

Even though the problem of finding the maximum element in a sequence is relatively trivial,
it provides a good illustration of the concept of an algorithm. Also, there are many instances
where the largest integer in a finite sequence of integers is required. For instance, a university
may need to find the highest score on a competitive exam taken by thousands of students. Or
a sports organization may want to identify the member with the highest rating each month.
We want to develop an algorithm that can be used whenever the problem of finding the largest
element in a finite sequence of integers arises.
We can specify a procedure for solving this problem in several ways. One method is simply to
use the English language to describe the sequence of steps used.We now provide such a solution.
Solution of Example 1: We perform the following steps.

1. Set the temporary maximum equal to the first integer in the sequence. (The temporary
maximum will be the largest integer examined at any stage of the procedure.)
2. Compare the next integer in the sequence to the temporary maximum, and if it is larger
than the temporary maximum, set the temporary maximum equal to this integer.
3. Repeat the previous step if there are more integers in the sequence.
4. Stop when there are no integers left in the sequence. The temporary maximum at this
point is the largest integer in the sequence.
▲

An algorithm can also be described using a computer language. However, when that is done,
only those instructions permitted in the language can be used. This often leads to a description
of the algorithm that is complicated and difficult to understand. Furthermore, because many
programming languages are in common use, it would be undesirable to choose one particular
language. So, instead of using a particular computer language to specify algorithms, a form
of pseudocode, described in Appendix 3, will be used in this book. (We will also describe
algorithms using the English language.) Pseudocode provides an intermediate step between

ABU JA‘FAR MOHAMMED IBN MUSA AL-KHOWARIZMI (C. 780 – C. 850) al-Khowarizmi, an as-
tronomer and mathematician, was a member of the House of Wisdom, an academy of scientists in Baghdad.
The name al-Khowarizmi means “from the town of Kowarzizm,” which was then part of Persia, but is now
called Khiva and is part of Uzbekistan. al-Khowarizmi wrote books on mathematics, astronomy, and geography.
Western Europeans first learned about algebra from his works. The word algebra comes from al-jabr, part of
the title of his book Kitab al-jabr w’al muquabala. This book was translated into Latin and was a widely used
textbook. His book on the use of Hindu numerals describes procedures for arithmetic operations using these
numerals. European authors used a Latin corruption of his name, which later evolved to the word algorithm, to
describe the subject of arithmetic with Hindu numerals.