0
$\begingroup$

When designing an algorithm for a given problem, sometimes I find it hard to foresee or clarify to myself what the boundary/edge/corner cases are. Not being able to come up with a decent number of the possible boundary/edge/corner cases causes one to make implicit assumptions about the problem at hand, which yields overlooked cases not to be accounted for, which is not good.

When reviewing the classic "Programming Challenges" by Steven S. Skiena and Miguel Revilla, one can read the following:

This is why it is so essential to review the specifications carefully. Even when you may be sure that your program is correct, the judge may keep saying no. Perhaps you are overlooking a boundary case or assuming something which just ain’t so. Resubmitting the program without change does you absolutely no good. Read the problem again to make sure it says what you thought it did.

I think it would be useful to sort come up with a method to, given a problem statement and the problem's input domain, assist the algorithm designer with unveiling boundary cases.

On one hand, knowing the upper and lower boundaries of your input data, helps you choose data types that can represent said values.

Another useful technique I do, is to ask myself, per each explicit assumption I can extract from the problem specification, what must exist for that assumption to be valid? For example, if I am told that all values will be given as a sorted array, does that mean that the given list will never be empty?

I would like to continue putting together a set of thumb rules to assist ourselves in uncovering boundary cases.

Improve this question
$\endgroup$
2
  • $\begingroup$ This sounds awfully broad. I'm not sure how to do that in general. It might be easier to answer in the context of a specific type of problem. In general, the site works best if there is a correct answer that can be explained in a few paragraphs; questions where you are looking for a long list don't always do well here. We'll see whether you get a good answer -- it is an interesting subject! $\endgroup$
    – D.W. ♦
    Commented Sep 3, 2017 at 18:29
  • 1
    $\begingroup$ You have the causality backwards. Making implicit assumptions is why you cannot come up with "corner" cases. The solution is to prove the algorithm correct (preferably in a machine-checked way). Technically, this won't help if you've misunderstood the requirements, but in practice it often does since it forces you to think carefully about what is being said. Of course, proving an algorithm correct (especially mechanically) is difficult. Nevertheless the attempt is often enough to clarify assumptions and having practice writing proofs gets you into the habit of not making such assumptions. $\endgroup$
    – Derek Elkins left SE
    Commented Sep 4, 2017 at 11:16

1 Answer 1

Reset to default
2
$\begingroup$

A good answer for this is over at Software Engineering https://softwareengineering.stackexchange.com/questions/72761/how-do-you-identify-edge-cases-on-algorithms

In general look at zero, empty string, max values, odd/even, nulls, sorted/random data where applicable including repeated testing with random data.

Also "think of everything that can go wrong" https://www.quora.com/How-do-you-identify-edge-cases-on-algorithms.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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