How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem instances, including a few simple "corner cases". This is a great heuristic: it's a great way to quickly weed out many incorrect attempts at an algorithm, and to gain understanding about why the algorithm doesn't work.

However, when learning algorithms, some students are tempted to stop there: if their algorithm works correctly on a handful of examples, including all of the corner cases they can think to try, then they conclude that the algorithm must be correct. There's always a student who asks: "Why do I need to prove my algorithm correct, if I can just try it on a few test cases?"

So, how do you fool the "try a bunch of test cases" heuristic? I'm looking for some good examples to show that this heuristic is not enough. In other words, I am looking for one or more examples of an algorithm that superficially looks like it might be correct, and that outputs the right answer on all of the small inputs that anyone is likely to come up with, but where the algorithm actually doesn't work. Maybe the algorithm just happens to work correctly on all small inputs and only fails for large inputs, or only fails for inputs with an unusual pattern.

Specifically, I am looking for:

-
An algorithm. The flaw has to be at the algorithmic level. I am not looking for implementation bugs. (For instance, at a bare minimum, the example should be language-agnostic, and the flaw should relate to algorithmic concerns rather than software engineering or implementation issues.)

-
An algorithm that someone might plausibly come up with. The pseudocode should look at least plausibly correct (e.g., code that is obfuscated or obviously dubious is not a good example). Bonus points if it is an algorithm that some student actually came up with when trying to solve a homework or exam proble

A common error I think is to use greedy algorithms, which is not always the correct approach, but might work in most test cases.

Example: Coin denominations, $d_1,\dots,d_k$ and a number $n$,
express $n$ as a sum of $d_i$:s with as few coins as possible.

A naive approach is to use the largest possible coin first,
and greedily produce such a sum.

For instance, the coins with value $6$, $5$ and $1$
will give correct answers with greedy for all numbers between $1$ and $14$
except for the number $10 = 6+1+1+1+1 = 5+5$.

StackExchange Computer Science Q#29475, answer score: 94