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’s 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. As we develop any new algorithm, we’ll naturally build up lots of intuition about the problem and how our algorithm solves it, and our informal reasoning will be guided by that intuition. However, 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 ...