Hunting for Counter ExamplesJanuary 7, 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"
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'
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?
What happens with very high values? and with very low ones?