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 ?
Best Answer
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.