I’ve come across the Knuth-Morris-Pratt (or KMP) string matching algorithm several times. Every time, I somehow manage to forget how it works within minutes of seeing it (or even implementing it).
Consider this variant of the classic Monty Hall problem (the one where “you should always change your mind because then you win with probability 2/3”):
I recently had to convince someone that generating “unique” IDs by (pseudo)randomly choosing numbers between 1 and 1,000,000,000 is a Bad Idea.
In the past, when confronted with something like this, I would wave my hands around, mumble…
We can compute the n-th Fibonacci number with only a logarithmic number of arithmetic operations! While I can think of zero practical applications, I still consider this an interesting exercise.