Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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:

  1. 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.)

  2. 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 problem.

  3. An algorithm that would pass a reasonable manual test strategy with high probability. Someone who tries a few small test cases by hand should be unlikely to discover the flaw. For instance, "simulate QuickCheck by hand on a dozen small test cases" should be unlikely to reveal that the algorithm is incorrect.

  4. Preferably, a deterministic algorithm. I've seen many students think that "try some test cases by hand" is a reasonable way to check whether a deterministic algorithm is correct, but I suspect most students would not assume that trying a few test cases is a good way to verify probabilistic algorithms. For probabilistic algorithms, there's often no way to tell whether any particular output is correct; and you can't hand-crank enough examples to do any useful statistical test on the output distribution. So, I'd prefer to focus on deterministic algorithms, as they get more cleanly to the heart of student misconceptions.

I'd like to teach the importance of proving your algorithm correct, and I'm hoping to use a few examples like this to help motivate proofs of correctness. I would prefer examples that are relatively simple and accessible to undergraduates; examples that require heavy machinery or a ton of mathematical/algorithmic background are less useful. Also, I don't want algorithms that are "unnatural"; while it might be easy to construct some weird artificial algorithm to fool the heuristic, if it looks highly unnatural or has an obvious backdoor constructed just to fool this heuristic, it probably won't be convincing to students. Any good examples?

share|improve this question
1  
I love your question, it's also related to a very interesting question i saw on Mathematics the other day related to disproving conjectures with large constants. You can find it here –  ZeroUltimax Aug 28 at 20:56
3  
Something about this question seems too localized or subjective. Maybe it's because what might be a hard-to-see flaw for me might be obvious to you, or vice versa. Similarly, what counts as contrived vs. natural is not entirely clear; if natural examples sprang to mind, coming up with ("contriving") one wouldn't be necessary. More generally, testing is inherently "hard to fool"; that's why companies pay people to do it, it works. –  Patrick87 Aug 28 at 21:15
1  
A nice restriction may be that tools like Quickcheck should not be able to reject correctness. (That specific task may be a post for Programming Puzzles & Code Golf?) –  Raphael Aug 29 at 10:41
2  
I'd ideally prefer an algorithm that (1) someone might plausibly come up with, and where the pseudocode looks plausibly correct (it's not obviously dubious/obfuscated), (2) is deterministic, (3) would pass a reasonable test strategy with high probability (e.g., at minimum, "simulate QuickCheck by hand" should be unlikely to show the algorithm is incorrect; of course, since we're doing it by hand, we might try only a dozen or so test cases, each small enough to hand-crank the algorithm) (the stronger the test strategy it can survive, the better the answer); (4) is language-agnostic. –  D.W. Aug 30 at 1:23
1  
@babou, I'm not talking about implementation bugs, but about flawed algorithms. –  D.W. Sep 4 at 23:50

11 Answers 11

up vote 17 down vote accepted

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$.

share|improve this answer
4  
This is indeed a good example, in particular one that students get routinely wrong. Not only do you need to pick particular coin sets but also particular values in order to see the algorithm fail. –  Raphael Sep 1 at 12:31
1  
In addition, let me say that students will also often have wrong proofs in this example (sporting some naive arguments that fail on closer examination), so more than one lesson can be learned here. –  Raphael Sep 3 at 11:12

I immediately recalled an example from R. Backhouse (this might have been in one of his books). Apparently, he had assigned a programming assignment where the students had to write a Pascal program to test equality of two strings. One of the programs turned in by a student was the following:

issame := (string1.length = string2.length);

if issame then
  for i := 1 to string1.length do
    issame := string1.char[i] = string2.char[i];

write(issame);

We can now test the program with the following inputs:

"university" "university" $\Rightarrow$ True; OK

"course" "course" $\Rightarrow$ True; OK

"" "" $\Rightarrow$ True; OK

"university" "course" $\Rightarrow$ False; OK

"lecture" "course" $\Rightarrow$ False; OK

"precision" "exactness" $\Rightarrow$ False, OK

All of this seems very promising: maybe the program does indeed work. But a more careful testing with say "pure" and "true" reveals faulty output. In fact, the program says "True" if the strings have the same length and the same last character!

However, testing had been pretty thorough: we had strings with different length, strings with equal length but different content, and even equal strings. Furthermore, the student had even tested and executed every branch. You can't really argue testing had been careless here -- given that the program is indeed very simple, it might be hard to find the motivation and energy to test it thoroughly enough.


Another cute example is binary search. In TAOCP, Knuth says that "although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky". Apparently, a bug in the binary search implementation of Java went unnoticed for a decade. It was an integer overflow bug, and only manifested with large enough input. Tricky details of binary search implementations are also covered by Bentley in the book Programming Pearls.

Bottom line: it can be surprisingly hard to be certain a binary search algorithm is correct by just testing it.

share|improve this answer
3  
Of course, the flaw is quite apparent from the source (if you have yourself written a similar thing before). –  Raphael Aug 29 at 10:54
    
Even if the simple flaw in the example program is corrected, strings give quite a bit of interesting problems! String reversal is a classic - the "basic" way of doing it is by simply reversing the bytes. Then encoding comes into play. Then surrogates (usually twice). The problem is, of course, that there's no easy way of formally proving your method is correct. –  Ordous Aug 29 at 16:02
1  
Maybe I am completely misinterpreting the question, but this seems to be a flaw in the implementation rather than a flaw in the algorithm itself. –  Mr.Mindor Aug 30 at 6:04
3  
@Mr.Mindor: how can you tell whether the programmer has written down a correct algorithm and then implemented it incorrectly, or written down an incorrect algorithm and then implemented it faithfully (I hesitate to say "correctly"!) –  Steve Jessop Sep 1 at 11:41
    
Is you second example (binary search) a bug as you actually state it, or is it a flawed algorithm. –  babou Sep 5 at 6:35

The best example I ever came across is primality testing:

input: natural number p, p != 2
output: is p a prime or not?
algorithm: compute 2**(p-1) mod p. If result = 1 then p is prime else p is not.

This works for (almost) every number, except for a very few counter examples, and one actually needs a machine to find a counterexample in a realistic period of time. The first counterexample is 341, and the density of counterexamples actually decreases with increasing p, although just about logarithmically.

Instead of just using 2 as the basis of the power, one may improve the algorithm by also using additional, increasing small primes as basis in case the previous prime returned 1. And still, there are counterexample to this scheme, namely the Carmichael numbers, pretty rare though

share|improve this answer
    
Fermat primality test is a probabilistic test, so your post-condition isn't correct. –  Femaref Aug 29 at 15:15
1  
ofc it is a probabilistic test but the answer nicely shows (more generally) how probabilistic algorithms mistaken for exact ones can be a source of error. more on Carmichael numbers –  vzn Aug 29 at 15:17
    
That's a nice example, with a limitation: for the practical use of primality testing that I'm familiar with, namely asymmetric cryptographic key generation, we use probabilistic algorithms! The numbers are too large for exact tests (if they weren't then they wouldn't be suitable for crypto because the keys could be found by brute force in realistic time). –  Gilles Aug 29 at 15:57
1  
the limitation you refer to is practical, not theoretical, and prime tests in crypto systems eg RSA are subject to rare/ highly improbable failures for exactly these reasons, again underlining the significance of the example. ie in practice sometimes this limitation is accepted as unavoidable. there are P time algorithms for primality testing eg AKS but they take too long for "smaller" numbers used in practice. –  vzn Aug 30 at 16:13

Here's one that was thrown at me by google reps at a convention I went to. It was coded in C, but it works in other languages that use references. Sorry for having to code on [cs.se], but it's the only to illustrate it.

swap(int& X, int& Y){
    X := X ^ Y
    Y := X ^ Y
    X := X ^ Y
}

This algorithm will work for any values given to x and y, even if they the same value. It will not work however if it's called as swap(x,x). In that situation, x ends up as 0. Now, this might not satisfy you, since you can somehow prove this operation to be correct mathematically, but still forget about this edge case.

share|improve this answer
    
That trick was used in the underhanded C contest to produce a flawed RC4 implementation. Reading that article again, I just noticed that this hack was probably submitted by @D.W. –  CodesInChaos Aug 29 at 9:47
4  
This flaw is indeed subtle -- but the flaw is language-specific, though, so it's not really a flaw in the algorithm; it's a flaw in the implementation. One could come up with other examples of language oddities that make it easy to conceal subtle flaws, but that wasn't really what I was looking for (I was looking for something at the level of abstraction of algorithms). In any case, this flaw isn't an ideal demonstration the value of proof; unless you're already thinking about aliasing, you might end up overlooking the same issue when you write out your "proof" of correctness. –  D.W. Aug 30 at 1:26
    
That'd why I'm surprise this got voted so high. –  ZeroUltimax Aug 30 at 21:04
    
@D.W. That's a matter of how what model you define the algorithm in. If you go down to a level where memory references are explicit (rather than the common model that assumes the absence of sharing), this is an algorithm flaw. The flaw isn't really language specific, it turns up in any language that supports sharing of memory refererences. –  Gilles Sep 18 at 18:51

There is a whole class of algorithms that is inherently hard to test: pseudo-random number generators. You can not test a single output but have to investigate (many) series of outputs with means of statistics. Depending on what and how you test you may well miss non-random characteristics.

One famous case where things went horribly wrong is RANDU. It passed the scrutiny available at the time -- which failed to consider the behaviour of tuples of subsequent outputs. Already triples show lots of structure:

Basically, the tests did not cover all use cases: while single-dimensional use of RANDU was (probably mostly) fine, it did not support using it to sample three-dimensional points (in this way).

Proper pseudo-random sampling is a tricky business. Luckily, there are powerful test suites there days, e.g. dieharder that specialise in throwing all the statistics we know at a proposed generator. Is it enough?

To be fair, I have no idea what you can feasibly prove for PRNGs.

share|improve this answer
1  
nice example however actually in general there is no way to prove any PRNG has no flaw, there is only an infinite hierarchy of weaker vs stronger tests. actually proving one is "random" in any strict sense is presumably undecidable (havent seen that proven though). –  vzn Aug 29 at 15:20
1  
That's a good idea of something that's hard to test, but RNG are also hard to prove. PRNG are not so much prone to implementation bugs as to being badly specified. Tests like diehard are good for some uses, but for crypto, you can pass diehard and still be laughed out of the room. There is no “proven secure” CSPRNG, the best you can hope is to prove that if your CSPRNG is broken then so is AES. –  Gilles Aug 29 at 15:55
    
@Gilles I was not trying to go into crypto, only statistical randomness (I think the two have pretty much orthogonal requirements). Should I make that clear in the answer? –  Raphael Aug 29 at 16:09
1  
Crypto randomness implies statistical randomness. Neither has a mathematically formal definition though, as far as I know, apart from the ideal (and contradictiory with the concept of a PRNG implemented on a deterministic Turing machine) notion of information-theoretic randomness. Does statistical randomness have a formal definition beyond ”must be independent from the distributions we'll test it against“? –  Gilles Aug 29 at 16:14
1  
@vzn: what it means to be a random sequence of numbers can be defined in many possible ways, but a simple one is "large Komolgorov complexity". In that case, it is easy to show that determining randomness is undecidable. –  cody Sep 2 at 20:47

A common mistake is to implement shuffling algorithms wrong. See discussion on wikipedia.

Trouble is that the bias is usually not easy to detect, and one needs to prove that there are indeed $n!$ "choices" done by the algorithm, and not $n^n$ or $(n-1)^n$ which are common for wrong implementations.

share|improve this answer
1  
It's a good bug, but not a good illustration of fooling the test cases heuristic, as testing doesn't really apply to a shuffling algorithms (it's randomized, so how would you test it? what would it mean to fail a test case, and how would you detect that from looking at the output?) –  D.W. Aug 31 at 17:26
    
You test it statistically of course. Uniform randomness is far from "anything can happen in the output". Would you not be suspicious if a program said to emulate a dice gave you 100 3's in a row? –  Per Alexandersson Aug 31 at 17:49
    
Again, I'm talking about the student heuristic of "try some test cases by hand". I've seen many students think that this is a reasonable way to check whether a deterministic algorithm is correct, but I suspect they would not assume it's a good way to test whether a shuffling algorithm is correct (since a shuffling algorithm is randomized, there's no way to tell whether any particular output is correct; in any case, you can't hand-crank enough examples by hand to do any useful statistical test). So I don't expect shuffling algorithms will help much to clear up the common misconception. –  D.W. Aug 31 at 19:39
1  
@PerAlexandersson: Even if you only generate only one shuffle it can't be truly random using MT with n > 2080. Now the deviation from expected will be very small, so you probably won't care... but this applies even if you generate far less than the period (as asmeurer points out above). –  Charles Sep 2 at 15:22
2  
This answer seems to have been made obsolete by Nikos M.'s more elaborate one? –  Raphael Sep 18 at 13:56

These are primality examples, because they're common.

(1) Primality in SymPy. Issue 1789. There was an incorrect test put on a well-known web site that didn't fail until after 10^14. While the fix was correct, it was just patching holes rather than rethinking the issue.

(2) Primality in Perl 6. Perl6 has added is-prime which uses a number of M-R tests with fixed bases. There are known counterexamples, but they're quite large since the default number of tests is huge (basically hiding the real problem by degrading performance). This will be addressed soon.

(3) Primality in FLINT. n_isprime() returning true for composites, since fixed. Basically the same issue as SymPy. Using the Feitsma/Galway database of SPRP-2 pseudoprimes to 2^64 we can now test these.

(4) Perl's Math::Primality. is_aks_prime broken. This sequence seems similar to lots of AKS implementations -- lots of code that either worked by accident (e.g. got lost in step 1 and ended up doing the entire thing by trial division) or didn't work for larger examples. Unfortunately AKS is so slow that it is difficult to test.

(5) Pari's pre-2.2 is_prime. Math::Pari ticket. It used 10 random bases for M-R tests (with fixed seed on startup, rather than GMP's fixed seed every call). It will tell you 9 is prime about 1 out of every 1M calls. If you pick the right number you can get it to fail relatively often, but the numbers become sparser, so it doesn't show up much in practice. They have since changed the algorithm and API.

This isn't wrong but it's a classic of probabilistic tests: How many rounds do you give, say, mpz_probab_prime_p? If we give it 5 rounds, it sure looks like it works well -- numbers have to pass a base-210 Fermat test and then 5 pre-selected bases Miller-Rabin tests. You won't find a counterexample until 3892757297131 (with GMP 5.0.1 or 6.0.0a), so you'd have to do a lot of testing to find it. But there are thousands of counterexamples under 2^64. So you keep raising the number. How far? Is there an adversary? How important is a correct answer? Are you confusing random bases with fixed bases? Do you know what input sizes you'll be given?

There is a related point: what is a big number? To students it seems many think 10,000 is a huge number. To many programmers, $10^{16}$ is a big number. To programmers working on cryptography, these are small, and big is, say 4096 bits. To programmers working on computational number theory, these are all small, and big might be 10 to 100 thousand decimal digits. To some mathematicians these all may be considered "not big" considering there are many more positive numbers larger than these examples than there are smaller. This is something a lot of people don't think about, but makes a difference when thinking about correctness and performance.

These are quite difficult to test correctly. My strategy includes obvious unit tests, plus edge cases, plus examples of failures seen before or in other packages, test vs. known databases where possible (e.g. if you do a single base-2 M-R test, then you've reduced the computationally infeasible task of testing 2^64 numbers to testing about 32 million numbers), and finally, lots of randomized tests using another package as a standard. The last point works for functions like primality where there is a fairly simple input and a known output, but quite a few tasks are like this. I have used this to find defects in both my own development code as well as occasional problems in the comparison packages. But given the infinite input space, we can't test everything.

As for proving correctness, here is another primality example. The BLS75 methods and ECPP have the concept of a primality certificate. Basically after they churn away doing searches to find values that work for their proofs, they can output them in a known format. One can then write a verifier or have someone else write it. These run very fast compared to the creation, and now either (1) both pieces of code are incorrect (hence why you'd prefer other programmers for the verifiers), or (2) the math behind the proof idea is wrong. #2 is always possible, but these have typically been published and reviewed by multiple people (and in some cases are easy enough for you to walk through yourself).

In comparison, methods like AKS, APR-CL, trial division, or the deterministic Rabin test, all produce no output other than "prime" or "composite." In the latter case we may have a factor hence can verify, but in the former case we're left with nothing other than this one bit of output. Did the program work correctly? Dunno.

It's important to test the software on more than just a few toy examples, and also going through some examples at each step of the algorithm and saying "given this input, does it make sense that I am here with this state?"

share|improve this answer
1  
Many of these look like either (1) implementation errors (the underlying algorithm is correct but it wasn't implemented correctly), which are interesting but not the point of this question, or (2) a deliberate, aware choice to select something that is fast and mostly works but might fail with very small probability (for code that's testing with one random base or a few fixed/random bases, I would hope that whoever choose to do that knew they were making a performance tradeoff). –  D.W. Aug 31 at 19:36
    
You are right on the first point -- correct algorithm + bug isn't the point, although the discussion and other examples are conflating them as well. The field is ripe with conjectures that work for small numbers but are incorrect. For point (2) that is true for some, but my examples #1 and #3 were not this case -- it was believed that the algorithm was correct (these 5 bases give proven results for numbers under 10^16), then later discovered that it was not. –  DanaJ Aug 31 at 19:58
    
Isn't this a fundamental issue with pseudo-primality tests? –  asmeurer Sep 2 at 4:25
    
asmeurer, yes in my #2 and the later discussion of them. But #1 and #3 were both cases of using Miller-Rabin with known bases to give deterministic correct results below a threshold. So in this case the "algorithm" (using the term loosely to match the OP) was incorrect. #4 isn't a probable prime test, but as DW pointed out, the algorithm works fine, it's just the implementation that is difficult. I included it because it leads to a similar situation: testing is needed, and how far do you go beyond simple examples before you say it works? –  DanaJ Sep 2 at 14:55
    
Some of your post seems to fit the question while some does not (cf D.W.'s comment). Please remove the examples (and other content) that does not answer the question. –  Raphael Sep 18 at 14:05

Fisher-Yates-Knuth shuffling algorithm is an (practical) example and one on which one of the the authors of this site has commented about.

The algorithm generates a random permutation of a given array as:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ i
       exchange a[j] and a[i]

One sees that in the loop the elements are swapped between $i$ and $j$, $0 \le j \le i$. This produces unbiased sampling of the permutations (no permutations are over-represented and others under-represented).

A "naive" algorithm could be:

 // To shuffle an array a of n elements (indices 0..n-1):
  for i from n − 1 downto 1 do
       j ← random integer with 0 ≤ j ≤ n-1
       exchange a[j] and a[i]

Where in the loop the element to be swapped is chosen from all available elements. However this produces biased sampling of the permutations (some are over-represented etc..)

Actually one can come-up with the fisher-yates-knuth shuffling using a simple (or naive) counting analysis.

The number of permutations of $n$ elements is $n! = n \times n-1 \times n-2 ..$, meaning 1st element can be placed in any of $n$ positions, 2nd element in remaining $n-1$ positions and so on.This is exactly what Fisher-Yates shuffle does and is why it produces un-biased (random) permutations (unlike the "naive" algorithm)

UPDATE: Per a comment, the main problem with verifying whether the shuffling algorithm is correct or not (biased or not) is that due to the statistics, a large number of samples is needed.

The linked codinghorror article explains exactly that (and with actual tests).

share|improve this answer
    
See here for an example correctness proof for a shuffle algorithm. –  Raphael Sep 18 at 13:54
    
You can improve your answer by explaining why/how the naive algorithm is hard to expose as wrong by testing. –  Raphael Sep 18 at 14:04
    
@Raphael, well the main problem is that this is statistical as such needs a large number of samples to verify. However the linked codinghorror article explains exactly that (and with actual tests). –  Nikos M. Sep 18 at 22:27

Pythons PEP450 that introduced statistics functions into the standard library might be of interest. As part of the justification for having a function that calculates the variance in the standard library of python the author Steven D'Aprano writes:

def variance(data):
        # Use the Computational Formula for Variance.
        n = len(data)
        ss = sum(x**2 for x in data) - (sum(data)**2)/n
        return ss/(n-1)

The above appears to be correct with a casual test:

>>> data = [1, 2, 4, 5, 8]
>>> variance(data)
  7.5

But adding a constant to every data point should not change the variance:

>>> data = [x+1e12 for x in data]
>>> variance(data)
  0.0

And variance should never be negative:

>>> variance(data*100)
  -1239429440.1282566
share|improve this answer
1  
If I decipher the syntax correctly, the algorithm is about correct (one might argue about dividing by $n-1$, but well). I assume the issue lies with with the implementation of the operations? Not sure if that fits the question: I think DW is looking for algorithmic mistakes, not "your algorithm can't deal with real hardware" mistakes. –  Raphael Aug 29 at 16:13
2  
@Raphael: Though to be fair, the chosen algorithm is well-known to be a poor choice for floating-point data. –  Hurkyl Sep 1 at 21:47
1  
It's not simply about the implementation of the operation about about numerics and how precision get's lost. If you want maximum precision then you have to order your operations in a certain way. That was one of the issue my numerics course at university was about. –  Christian Sep 18 at 14:27
    
In addition to Raphael's accurate comment, a shortcoming of this example is that I don't think a proof of correctness would help avoid this flaw. If you're not aware of the subtleties of floating-point arithmetic, you might think you have proven this correct (by proving that the formula is valid). So it's not an ideal example to teach students why it is important to prove their algorithms correct. If students saw this example, my suspicion is they would instead draw the lesson "floating point / numeric computation stuff is tricky". –  D.W. Sep 19 at 3:20

While this is likely not quite what you're after, it's certainly easy to understand and testing some small cases without any other thinking will lead to an incorrect algorithm.

Problem: Write a function that takes a nonnegative integer $n$ and returns the number of proper divisors of $n^2+n+41$, namely the number of integers $0<d$ for which $d\text{ divides } n^2+n+41$ and $d < n^2+n+41$.

Proposed solution:

int f(int n) {
   return 1;
}

This happens to be correct for $n= 0, 1, 2, \dotsc, 39$ but fails when $n=40$.

This "try some small cases and infer an algorithm from the result" approach crops up frequently (though not as extremely as here) in programming competitions where the pressure is to come up with an algorithm that (a) is quick to implement and (b) has a fast run time.

share|improve this answer
4  
I don't think this is a very good example, because few people would attempt to find the divisors of a polynomial by returning 1. –  Brian S Aug 29 at 15:08
1  
Suppose the problem asked to determine for a given integer $n$ whether 3 divided $n^3-n$. A correct solution for this problem is a function which returns true for any input. Is this significantly different from the example I gave? –  Rick Decker Aug 29 at 16:43
    
This could be relevant, in the sense that returning a constant value for divisors (or another caclulation), can be the result of a wrong algorithmic approach to a problem (for example a statistical problem, or not handling edge cases of the algorithm). However the answer needs rephrasing –  Nikos M. Sep 18 at 22:42
    
@NikosM. Heh. I feel like I'm beating a dead horse here, but the question's second paragraph says that "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?" In this instance, for the first 40 values (far more than a student is likely to try), returning 1 is correct. It seems to me to be that's what the OP was looking for. –  Rick Decker Sep 18 at 23:54
    
Ok, yeah, but this as phrased is trivial (maybe typicaly correct), but not in the spirit of the question. Still would need rephrasing –  Nikos M. Sep 19 at 4:03

One of the worst cases I recently encountered myself was in a Artificial Neural Network. Like many machine learning problems, these are especially hard to debug because it is entirely normal for them to produce the "wrong" output. For instance, in digit recognition, a student's implementation may very well score 85% right - for a correct implementation (!)

For those of you who aren't familiar with neural networks, the usual way to train neural networks is by a backpropagation algorithm. You connect all nodes in the network using random weights, calculate the results for all inputs, compare that to the desired outputs, and propagate the errors backwards towards the weights.

Well, as I'd written the code in Octave, I managed to sneak in a one-off error as Octave arrays start at 1, and node 1 in this neural network was a special case so the first normal node was 2. Unusual, but that's how I should have programmed it. As a result, in neural network training I missed node 1, but the other nodes together almost always dominated node 1 and the result was perhaps 1% off. But 84% was still a believable result. I only caught it because I did realize that node 1 wasn't trained, but still had it's initial (random) value. I realized that special or not, its value should be set by training.

share|improve this answer
1  
I don't think this really answers the question. The question is about algorithms that appear correct but aren't because of, for example, some special case that comes up only rarely. You don't seem to be talking about an incorrect algorithm but, rather, an incorrect implementation of a correct algorithm (i.e., a bug). –  David Richerby Sep 1 at 23:12
1  
@DavidRicherby: Two sides of a coin, really. The network training code I implemented was a correct implementation of my understanding of the backpropagation algorithm. My code worked and produced results on simple use cases far better than random - it's a valid training algorithm for an alomost-identical network. But these special nodes exist to deal with biased input which I didn't try. And the actual test case needed to detect this is seeing how much the performance drops by biasing the inputs. –  MSalters Sep 1 at 23:45

protected by Community Sep 18 at 19:05

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.