Describing Algorithms

Effective algorithm design and description

The skills required to effectively design and analyze algorithms are entangled with the skills required to describe algorithms effectively. A complete description of any algorithm has four components:

• What: A precise specification of the problem that the algorithm solves
• How: A precise description of the algorithm itself
• Why: A proof that the algorithm solves the problem it is supposed to solve
• How fast: An analysis of the running time of the algorithm

It is not necessary (or even advisable) to develop these four components in this particular order. Problem specifications, algorithm descriptions, correctness proofs, and time analyses usually evolve simultaneously, with the development of each component informing the development of the others. For example, we may need to tweak the problem description to support a faster algorithm or modify the algorithm to handle a tricky case in the proof of correctness. Nevertheless, presenting these components separately is usually clearest for the reader.

As with any writing, it’s important to aim our descriptions at the right audience; we recommend writing for a competent but skeptical programmer who is not as clever as we are. Let’s think of ourselves from six months ago. As we develop any new algorithm, we will naturally build up lots of intuition about the problem and about how our algorithm solves it, and our informal reasoning will be guided by that intuition. But anyone reading our algorithm later, or the code we derive from it, won’t share our intuition or experience. Neither will our compiler. Neither will we six months from now. All they will have is our written description.

Even if we never have to explain our algorithms to anyone else, it’s still important to develop them with an audience in mind. Trying to communicate clearly forces us to think more clearly. In particular, writing for a novice audience, who will interpret our words exactly as written, forces us to work through fine details, no matter how “obvious” or “intuitive” our high-level ideas may seem at the moment. Similarly, writing for a skeptical audience forces us to develop robust arguments for correctness and efficiency instead of trusting our intuition or our intelligence.

We cannot emphasize this point enough. Our primary job as algorithm designers is teaching other people how and why our algorithms work. If we can’t communicate our ideas to other human beings, they may as well not exist. Producing correct and efficient executable code is an important but secondary goal. Convincing ourselves, our professors, our (prospective) employers, our colleagues, or our students that we are smart is at best a distant third.

Specifying the problem

Before we can even start developing a new algorithm, we have to agree on what problem our algorithm is supposed to solve. Similarly, before we can even start describing an algorithm, we have to describe the problem that the algorithm is supposed to solve. Algorithmic problems are often presented using standard English in terms of real-world objects. It’s up to us, the algorithm designers, to restate these problems in terms of formal, abstract, mathematical objects—numbers, arrays, lists, graphs, trees, and so on—that we can reason about formally. We must also determine if the problem statement carries any hidden assumptions and state those assumptions explicitly. (For example, in the song “$n$ Bottles of Beer on the Wall”, $n$ is always a non-negative integer.)

We may need to refine our specifications as we develop the algorithm. For example, our algorithm may require a particular input representation, or produce a particular output representation, that was left unspecified in the original informal problem description. Or our algorithm might actually solve a more general problem than we were originally asked to solve. (This is a common feature of recursive algorithms.)

The specification should include just enough detail that someone else could use our algorithm as a black box, without knowing how or why the algorithm actually works. In particular, we must describe the type and meaning of each input parameter, and exactly how the eventual output depends on the input parameters. On the other hand, our specification should deliberately hide any details that are not necessary to use the algorithm as a black box. Let that which does not matter truly slide.

For example, the lattice and duplation-and-mediation algorithms both solve the same problem: Given two non-negative integers $x$ and $y$, each represented as an array of digits, compute the product $x · y$, also represented as an array of digits. To someone using these algorithms, the choice of algorithm is completely irrelevant. On the other hand, the Greek straightedge-and-compass algorithm solves a different problem because the input and output values are represented by line segments instead of arrays of digits.

Describing the algorithm

Computer programs are concrete representations of algorithms, but algorithms are not programs. Rather, algorithms are abstract mechanical procedures that can be implemented in any programming language that supports the underlying primitive operations. The idiosyncratic syntactic details of our favorite programming language are utterly irrelevant; focusing on these will only distract us (and our readers) from what’s really going on. A good algorithm description is closer to what we should write in the comments of a real program than the code itself. Code is a poor medium for storytelling.

On the other hand, a plain English prose description is usually not a good idea either. Algorithms have lots of idiomatic structures—especially conditionals, loops, function calls, and recursion—that are far too easily hidden by unstructured prose. Colloquial English is full of ambiguities and shades of meaning, but algorithms must be described as unambiguously as possible. Prose is a poor medium for precision.

For many, the clearest way to present an algorithm is by using a combination of pseudocode and structured English. Pseudocode uses the structure of formal programming languages and mathematics to break algorithms into primitive steps; the primitive steps themselves can be written using mathematical notation, pure English, or an appropriate mixture of the two, whatever is clearest. Well-written pseudocode reveals the internal structure of the algorithm but hides irrelevant implementation details, making the algorithm easier to understand, analyze, debug, and implement.

Whenever we describe an algorithm, our description should include every detail necessary to fully specify the algorithm, prove its correctness, and analyze its running time. At the same time, it should exclude any details that are not necessary to fully specify the algorithm, prove its correctness, and analyze its running time. (So we can let them slide.) At a more practical level, our description should allow a competent but skeptical programmer who has not read this book to quickly and correctly implement the algorithm in their favorite programming language without understanding why it works.

We don’t want to bore you with the rules we follow for writing pseudocode, but we must caution against one especially pernicious habit. Never describe repeated operations informally, as in, “Do [this] first, then do [that] second, and so on.” Or “Repeat this process until [something].” As anyone who has taken one of those frustrating “What comes next in this sequence?” tests already knows, describing the first few steps of an algorithm says little or nothing about what happens in later steps. If our algorithm has a loop, write it as a loop, and explicitly describe what happens in an arbitrary iteration. Similarly, if our algorithm is recursive, write it recursively, and explicitly describe the case boundaries and what happens in each case.