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 ...