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 you are. Think of yourself six months ago. As you develop any new algorithm, you will naturally build up lots of intuition about the problem and about how your algorithm solves it, and your informal reasoning will be guided by that intuition. But anyone reading your algorithm later, or the code you derive from it, won’t share your intuition or experience. Neither will your compiler. Neither will you yourself six months from now. All they will have is your 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 ...