How to determine most challenging test-cases to test any algorithm?

Question

While solving any problem, we write algorithms. Some efficient, some not, some work, some fail. But sometimes we end up writing something which is mostly a success when we do a dry test run, perhaps, the way we frame the test data is prejudiced, but the algorithm fails in some other cases.

For some algorithms , the nature of data can be diverse and magnitude large, for example like the problem:

Find the maximum subsequence sum of an array of integers which contains both positive and negative numbers and return the starting and ending indices within the array.

Can anyone tell me is there any specific and generic thumb rule by which we can design the most stringent of test cases to test the correctness of algorithms like this one ?

Answer 1

I will assume we are talking about a reasonably complex algorithm, i.e., one where you'd usually get out pen and paper and need quite some time before you arrive at the pseudocode for a solution.

In such a scenario, the most challenging test cases are the edge cases you probably didn't think of. Here, test-driven design can only get you so far, as the test coverage is severely limited by your imagination. In these cases, I try a branch-based approach. I try to create input sequences that will hit all possible control flow variations and assert important properties that help me believe that the algorithm is in fact correct.

The important thing is that for algorithmic problems, there is usually quite a high density of edge cases. It is easier to find out what these edge cases are if you can look at the algorithm, i.e., do whitebox testing. In TDD, you'd do the opposite: ideally, you write all your test cases before you even start implementing the code. However, if the problem was algorithmically challenging, you probably already made sure that your algorithm would return the correct solution for all instances that you managed to come up with upfront.

Answer 2

While I agree with Robert Harvey's statement, that test driven development is a useful approach, I often do get the impression that people think that with sufficiently many unit tests in place they are on the safe side and are allowed to stop thinking about useful tests. This, I think, is far from being true.

In my opinion creating reasonable tests is something between an art and good craftmansship, where knowing about existing tools and best practices together with thouroghly and correctly applying them is the craftmanship part. Good knowledge about common programming errors as an additional ingredient will also help to find useful tests. But you also have to understand the problem solved by the algorithm and need to get an idea of where an implementation is likely to fail. You will, at least partially, often be on your own here. I'd try to find at least one alternative algorithm and run them concurrently. Often you choose a specific one for performance -- in automated test you may use a slower one for croos checking. Whatever helps is somehting you can put into the best practices box.

Without spending too much time on it, for the problem you gave as an example I'd try to find an (automated) way to (randomly) create (many) sequences of varying length for which I can predict the result. Then feed them into the algorithm, and log the input in case it fails. In addition I'd do that for a fixed (not random) set of sequences as a protection against code changes which might break the code. I'd make sure there will be sequences with more than one solution and try to figure out whether sequences with overlapping solutions exist and if yes, try to create some of them, as well.

I'd like to add that for me, as a mathematician, an algorithm is either correct or wrong for at least one set of input data and it is something for which you can (often) give prove (the link is more or less randomly chosen) -- of course there is always the human factor....But even if you believe that, you cannot do that (give proof) for an implementation of a (sufficiently complex) algorithm, which is the thing which is actually under test.

Edit I think an example which is sufficiently obvious and elaborate at the same time might be useful. For this I'd like to draw your attention to Knuth's 'The art of computer programming' vol 2, where under the heading 'The classical algorithms' an algorithm is presented which shows how to divide an (arbitrary) positive integer by another positive integer. Knuth actually gives (a somewhat hard to understand) proof of why his algorithm is correct. A certain part of that proof shows that there is a straightforward way of performing a certain task in that algorithm and an exceptional case. The exceptional case (see step D3 in algorithm D if you really want to look it up) occurs extremely rarely and, actually, requires a more complex calculation.

Now while there is a quite obvious way to create unit tests for this algorithm (apply it to two integers and then perform the reverse operation to check whether you get to from where you started) it is absolutely not obvious how to make sure the exceptional case is tested. First you need to know about it (that is, you have to understand the hairy details of the proof of the algorithm), then you need to find data for which it will actually occur. Doing the whole chain (finding the algorithm, which is, in this case, done for you by the author, finding a proof for it, identifying the exceptional cases and making sure test data is found which test this as well) is not covered by any kind of best practice.

Answer 3

As @Thomas has pointed out, designing good test cases needs experience. But there is good news for you: you can learn it, and there are a lot of books out there where systematic approaches are described. For example, a "classic" one is "The Art of Software Testing, Second Edition" by Glenford Myers.

Some examples for techniques described there

• code coverage / branch coverage tests: create a set of test cases so that every line of code is executed, or every possible branch is executed (this is a white-box technique for a program where you have inside into the source code)
• equivalence class: partition your space of input data into disjoint classes, and create at least one test case for each class
• edge case analysis: in your example above that may mean to create a test case with an empty array, a one-element array, a two-element array, an array with just positive, just negative elements or just zeros etc.

So, the answer to your question is: there is not just "one" rule of thumb, there are many, and you should have a look into additional literature to learn them.

Answer 4

The best way that I know of is to write programs using the Test-Driven-Development methodology. By writing your test cases first, and then only writing code that makes your test cases pass, your algorithms will only implement your test cases, and therefore your code will have 100% coverage.

That's a bit tongue-in-cheek, of course. Writing test cases and code that passes those test cases doesn't guarantee that your code won't have edge behavior beyond the test cases, and I still don't believe that you can simply grow a sensible architecture from the ground up using only red-green-refactor.

The way out is not to find the best possible testing algorithms (although that is certainly a good thing to do). Rather, use best programming practices and design your programs in such a way that the amount of unexpected behavior is minimized. Learning how to do that is the ongoing life and learning of every professional programmer.

You can also use code coverage tools to identify test cases.