The Algorithm Design Manual Second Edition

1.3

Reasoning about Correctness

Hopefully, the previous examples have opened your eyes to the subtleties of algo-

rithm correctness. We need tools to distinguish correct algorithms from incorrect

ones, the primary one of which is called a proof.

A proper mathematical proof consists of several parts. First, there is a clear,

precise statement of what you are trying to prove. Second, there is a set of assump-

tions of things which are taken to be true and hence used as part of the proof.

Third, there is a chain of reasoning which takes you from these assumptions to the

statement you are trying to prove. Finally, there is a little square ( ) or QED at the

bottom to denote that you have finished, representing the Latin phrase for “thus

it is demonstrated.”

This book is not going to emphasize formal proofs of correctness, because they

are very difficult to do right and quite misleading when you do them wrong. A

proof is indeed a demonstration. Proofs are useful only when they are honest; crisp

arguments explaining why an algorithm satisfies a nontrivial correctness property.

---

12

1 .

I N T R O D U C T I O N T O A L G O R I T H M D E S I G N

Correct algorithms require careful exposition, and efforts to show both cor-

rectness and not incorrectness. We develop tools for doing so in the subsections

below.