Page 214 - Discrete Mathematics and Its Applications

3.1 Algorithms 193

an English language description of an algorithm and an implementation of this algorithm in a
programming language. The steps of the algorithm are specified using instructions resembling
those used in programming languages. However, in pseudocode, the instructions used can
include any well-defined operations or statements. A computer program can be produced in
any computer language using the pseudocode description as a starting point.
The pseudocode used in this book is designed to be easily understood. It can serve as an
intermediate step in the construction of programs implementing algorithms in one of a variety of
different programming languages.Although this pseudocode does not follow the syntax of Java,
C, C++, or any other programming language, students familiar with a modern programming
language will find it easy to follow. A key difference between this pseudocode and code in a
programming language is that we can use any well-defined instruction even if it would take
many lines of code to implement this instruction. The details of the pseudocode used in the text
are given in Appendix 3. The reader should refer to this appendix whenever the need arises.
A pseudocode description of the algorithm for finding the maximum element in a finite
sequence follows.

ALGORITHM 1 Finding the Maximum Element in a Finite Sequence.

procedure max(a 1 ,a 2 ,...,a n : integers)
max := a 1
for i := 2 to n
if max <a i then max := a i
return max{max is the largest element}

This algorithm first assigns the initial term of the sequence, a 1 , to the variable max. The “for”
loop is used to successively examine terms of the sequence. If a term is greater than the current
value of max, it is assigned to be the new value of max.

PROPERTIES OF ALGORITHMS There are several properties that algorithms generally
share. They are useful to keep in mind when algorithms are described. These properties are:
Input. An algorithm has input values from a specified set.
Output. From each set of input values an algorithm produces output values from a spec-
ified set. The output values are the solution to the problem.
Definiteness. The steps of an algorithm must be defined precisely.
Correctness. An algorithm should produce the correct output values for each set of input
values.
Finiteness. An algorithm should produce the desired output after a finite (but perhaps
large) number of steps for any input in the set.
Effectiveness. It must be possible to perform each step of an algorithm exactly and in a
finite amount of time.
Generality. The procedure should be applicable for all problems of the desired form, not
just for a particular set of input values.

EXAMPLE 2 Show that Algorithm 1 for finding the maximum element in a finite sequence of integers has all
the properties listed.

Solution: The input to Algorithm 1 is a sequence of integers. The output is the largest integer
in the sequence. Each step of the algorithm is precisely defined, because only assignments, a
finite loop, and conditional statements occur. To show that the algorithm is correct, we must
show that when the algorithm terminates, the value of the variable max equals the maximum