Evaluating Solutions to Maximum Pairwise Product Problem

Stress testing

We’ll now introduce stress testing—a technique for generating thousands of tests to find a test case for which our solution fails.

A stress test consists of four parts:

• Implementation of an algorithm.
• An alternative, trivial, and slow but correct implementation of an algorithm for the same problem.
• A random test generator.
• An infinite loop in which a new test is generated and fed into both implementations to compare the results. If their results differ, the test and both answers are output, and the program stops. Otherwise, the loop repeats.

The idea behind stress testing is that two correct implementations should give the same answer for each test (provided the answer to the problem is unique). However, if one of the implementations is incorrect, then there exists a test on which their answers differ.

The only case when it is not so is when there is the same mistake in both implementations, but that is unlikely (unless the mistake is somewhere in the input/output routines, which are common to both solutions).

Indeed, if one solution is correct and the other is wrong, then a test case exists in which they differ. If both are wrong, but the bugs are different, then there is a test for which two solutions give different results.

Trivial implementation

Here is the stress test for $MaxPairwiseProductFast$ using $MaxPairwiseProductNaive$ as a trivial implementation:

---

 $StressTest(N,M)$:
 while $true$:
       $n \leftarrow$ random integer between $2$ and $N$
       allocate array $A[1...n]$
       for $i$ from $1$ to $n$:
             $A[i] \leftarrow$ random integer between $0$ and $M$
       print($A[1...n]$
       $result_{1} \leftarrow$ $MaxPairwiseProductNaive(A)$
       $result_{2} \leftarrow$ $MaxPairwiseProductFast(A)$
       if $result_{1} = result_{2}$:
              print (“OK”) ...