Algorithms - Writing for Computer Science - page 140

In summary, in the presentation of an algorithm it is usual to give a formal
demonstration of correctness and performance, and perhaps an experimental valida-
tion. When such demonstrations are absent, the reason for the absence should be clear.

Formalisms

The description of an algorithm usually consists of the algorithm itself and the envi-
ronment it requires. There are several common formalisms for presenting algorithms.
One is the list style, in which the algorithm is broken down into a series of numbered
or named steps and loops involving several steps are represented by “go to step X”
statements. This form has the advantage that the algorithm can be discussed as it
is presented: there is no restriction on the amount of text used to describe a step
(although a step should be a single activity), so there is room for a clear statement of
each step and for remarks on its properties. But the control structure is often obscure
and it is all too easy for the discussion to bury the algorithm.
Another common formalism is pseudocode , in which the algorithm is presented
as if written in a block-structured language and each line is numbered. An example is
shown in Fig. 10.1 . Pseudocode has the advantage that the structure of the algorithm
is immediately obvious; but each statement is forced by formatting considerations
to be fairly terse, and it is not easy to include detailed comments. Also, the use of
programming language constructs and notation is usually a mistake. It takes experi-
ence to present algorithms well in pseudocode, and, although it is straightforward to
translate such pseudocode into an imperative programming language, pseudocode is
unnecessarily difficult to understand.
A better option is to use what might be called prosecode , in which the algorithm is
described by text with embedded code, rather than as code with textual annotations;
structure is given by numbered lists in which loops are presented as sublists with
nested numbering. An example is shown in Fig. 10.2 . In the example, input and
output are described in the preamble, and “code” statements and explanatory text are
mixed freely in the algorithm itself. Despite the informality, the specification of the
algorithm is direct and clear. The assignment symbol “ ₐ ” is a good choice because

it is unambiguous, in contrast to “ ”. However, the prosecode style of presentation

is only effective when the concepts underlying the algorithm have been discussed
before the algorithm is given.
Another effective approach to description of algorithms is what might be called
literate code , in which the detail of the algorithm is introduced gradually, inter-
mingled with discussion of the underlying ideas and perhaps with the asymptotic
analysis and proof of correctness. An example is shown in Fig. 10.3 . (This example
is incomplete—most algorithms worth presenting need a substantial explanation that
can't be condensed into a page or two.)

=