34

Basically how do you find out which could be your worst or best case and any other "edge" cases you might have BEFORE having them and so, how do you prepare your code for them?

1
  • 5
    Alternative: when possible, I am a huge fan of fuzzy testing. It's amazing how the sheer mass of randomly generated inputs can spot bugs within a function that no amount of scrutiny / edge-testing revealed. The two work really well together... and they are obviously complemented by logging errors accurately when running on "true" inputs :) May 2, 2011 at 19:37

6 Answers 6

37

Based on the content of the algorithm you can identify what data structures/types/constructs are used. Then, you try to understand the (possible) weak points of those and try to come up with an execution plan that will make it run in those cases.

For example, the algorithm takes a string and an integer as input and does some sorting of the characters of the string.

Here we have:

String with some known special cases:

  • Empty string
  • Long string
  • Unicode string (special characters)
  • If limited to a specific set of characters, what happens when some are not in the range
  • Odd/even length string
  • Null (as argument)
  • Non-null terminated

Integer with known special cases:

  • 0
  • Min/MaxInt
  • Negative/Positive

Sort algorithm that could fail in the following boundary cases:

  • Empty input
  • 1 element input
  • Very long input (maybe of length max(data type used for index))
  • Garbage inside the collection that will be sorted
  • Null input
  • Duplicate elements
  • Collection with all elements equal
  • Odd/even length input

Then, take all these cases and create a long list trying to understand how they overlap. Ex:

  • Empty string case covers the empty collection case
  • Null string == null collection
  • etc.

Now create test cases for them :)

Short summary: break the algorithm in basic blocks for which you know the boundary cases and then reassemble them, creating global boundary cases

1
  • 6
    One more thing to add . . . analyze the code and look for special cases in the code. If the developer handles 0 to 13 differently than 14 and greater - maybe the dev is using different algorithms for small and large values for performance reasons - you have edge cases at 13 and 14. +1 for great list. May 3, 2011 at 18:19
6

An "edge" has two meanings, and both are relevant when it comes to edge cases. An edge is either an area where a small change in the input leads to a large change in the output, or the end of a range.

So, to identify the edge cases of an algorithm, I first look at the input domain. Its edge values could lead to edge cases of the algorithm.

Secondly, I look at the output domain, and look back at the input values that might create them. This is less commonly a problem with algorithms, but it helps find problems in algorithms that are designed to generate output which spans a given output domain. E.g. a random-number generator should be able to generate all intended output values.

Finally, I check the algorithm to see if there are input cases which are similar, yet lead to dissimilar outputs. Finding these edge cases is the hardest, because it involves both domains and a pair of inputs.

2

I don't think there is any algorithm to determine edge conditions....just experience.

Example: for a byte parameter you would want to test numbers like 0, 127, 128, 255, 256, -1, anything that can cause trouble.

0

Part of the skill of using algorithms is knowing their weaknesses and patholigical cases. Victor's answer gives some good tips, but in general I would advise that you need to study the topic in more depth to get a feel for this, I don't think you can follow rules of thumb to answer this question fully. E.g. see Cormen, or Skiena (Skiena in particular has a very good section on where to use algorithms and what works well in certain cases, Cormen goes in to more theory I think).

0

Ensuring correctness becomes easy with proper structuring of the code itself. Break down the algorithm implementation into simple procedures or functions that, do one, simple thing at a time. You can independently fuzz test these with tricky inputs. The answer by @victor points a few such values.

Often, these simpler parts turn out to be common tasks like: finding minimum/maximum, flipping variables, finding mid-point, median, average, rounding off, reversing, the usual math.stuff and so on.

-1

This is a very general question so all I can do is throw out some general, vague ideas :)

-Examine boundary cases. Ex. if you're parsing a string what happens if the string is empty or null? If you're counting from x to y what happens at x and y?
-Code that could be simplified or D.R.Y.-ed out. Any unneeded complexity could add to things that could go wrong.

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