Hunting for Counter Examples

January 6, 2019

Lately I have been reading The Algorithm Design Manual (also known as "Skiena’s big red book"), a good introductory book to algorithms by professor Steve Skiena.

The book is awesome, and one of the main topics is the correctness of the algorithms. In the first chapter of the book, professor Skiena drafts a very short description of how to "hunt for counter examples".

Those are very simple, straightforward, and one may say obvious set of five as I found my self implementing many times most of this points, but in a erratic manner: never implementing all at once.

I wanted to list the points here and have it at hand after basically sending any pull request from now on.

Without more introduction, here are...

The "five rules"

Think small

Small examples are simpler to reason about

G. Polya suggests in his great book 'How to solve it' more on this topic:

And there's much more, I'd recommend you the sections 'DECOMPOSING AND RECOMBINING', 'SPECIALIZATION' and 'ANALOGY'

Think exhaustively

Try to find all non-trivial possibilities

Hunt for the weakness

What things the algorithm proposes/assumes? Example: if the algorithm is proposing to take the biggest thing in the collection, try to reason scenarios when that may be the wrong thing to do.

Go for a tie

What happens if all values are the same?

Seek extremes

What happens with very high values? and with very low ones?