The Algorithm Design Manual Second Edition

1.3.1

Expressing Algorithms

Reasoning about an algorithm is impossible without a careful description of the

sequence of steps to be performed. The three most common forms of algorithmic

notation are (1) English, (2) pseudocode, or (3) a real programming language.

We will use all three in this book. Pseudocode is perhaps the most mysterious of

the bunch, but it is best defined as a programming language that never complains

about syntax errors. All three methods are useful because there is a natural tradeoff

between greater ease of expression and precision. English is the most natural but

least precise programming language, while Java and C/C++ are precise but diffi-

cult to write and understand. Pseudocode is generally useful because it represents

a happy medium.

The choice of which notation is best depends upon which method you are most

comfortable with. I usually prefer to describe the ideas of an algorithm in English,

moving to a more formal, programming-language-like pseudocode or even real code

to clarify sufficiently tricky details.

A common mistake my students make is to use pseudocode to dress up an ill-

defined idea so that it looks more formal. Clarity should be the goal. For example,

the ExhaustiveScheduling algorithm on page

10

could have been better written

in English as:

ExhaustiveScheduling(I)

Test all 2

n

subsets of intervals from I, and return the largest subset

consisting of mutually non-overlapping intervals.

Take-Home Lesson: The heart of any algorithm is an idea. If your idea is

not clearly revealed when you express an algorithm, then you are using too

low-level a notation to describe it.