0:00

The previous video ended on an unsuccessful attempt to submit our

solution to the max pairwise product problem.

Even worse, we don't know what is the test on which our program fails

because the system doesn't show it to us.

This is actually a pretty standard situation when

solving algorithmic programming assignments.

In this, and the next few videos, we will learn how to overcome this situation and

to even avoid it in the first place.

I will explain to you and

show you in action a powerful technique called stress testing.

By the end, you will be able to implement a stress test for

your solution of an algorithmic problem, use it to find a small and

easy test on which your program fails, debug your program, and

make sure it works correctly afterwards with high confidence.

Also, you will be able to list and apply the set of standard testing techniques,

which should be always applied when solving algorithmic programming

assignments.

So what is stress testing?

In general, it is a program that generates random tests in an infinite loop, and

for each test, it launches your solution on this test and

an alternative solution on the same test and compares the results.

This alternative solution you also have to invent and implement yourself, but

it is usually easy, because it can be any simple, slow, brute force solution, or

just any other solution that you can come up with.

The only requirement is that it should be significantly

different from your main solution.

1:25

Then you just wait until you find a test on which your solutions differ.

If one of them is correct and another is wrong, then it is guaranteed to happen,

because there is some test for which your wrong solution gives the wrong answer, and

your correct solution gives correct answer, and so they differ.

If, however, both of your solutions are wrong, which also happens often,

they are still almost guaranteed to have some test on which one of them gives

wrong answer and another one gives correct answer because they're probably

wrong in different places.

When you find a test on which your solutions' answers differ,

you can determine which one of them returns wrong answer and

debug it, fix it, and then repeat the stress testing.

Now let's look at the practical implementation.

I've already implemented the stress test for this problem.

It is in the file called stress_test.cpp.

Let's look into that.

So it is almost the same as the solution that we've sent

in the previous video, but I've added some things.

First, we add this #include <cstd.lib>.

And this include just allows us to use a part of

standard library to generate some random numbers.

And we will use it to generate some random tests automatically.

Then we have the same code of two functions,

MaxPairwiseProduct and MaxPairwiseProductFast,

which we used in our last solution which was submitted in the system.

But now in the main function, we have a whole additional while loop.

3:09

Here it is, and this is where the stress test itself is.

So what do we do in principle is we generate some random tests,

then we launch both solutions, MaxPairwiseProduct and

MaxPairwiseProductFast on this random test, and we compare the results.

And the idea is if you have a correct solution and another correct solution and

the correct answer for your problem is the only correct answer,

then any two correct solutions will give the same answers for any test.

And if you have some wrong solution and some correct solution,

then on some tests, their answers will differ.

And also if you have two wrong solutions, then probably they're

wrong in a different way, and then there will also be some test,

hopefully, on which their answers differ.

If you generate a lot of tests, then with some probability, at some point,

you will generate a test for which the answers of the solutions differ.

You can detect that situation, and then look at the input test and at the answers.

4:28

And you can determine which of the algorithms was right, and which was wrong,

maybe both were wrong.

But anyway, you will find at least one of the algorithms which are wrong because if

their answers are different, then at least one of them gives wrong answer.

And then you will be able to debug that algorithm,

fix the bug, and then run the stress test again.

And either, you will again find some difference, or

you won't find any difference anymore, and then hopefully,

you fixed all the bugs in all the solutions, and you can submit it.

So how it works in practice.

First, we need to generate the test for our problem.

We'll start with generating number n, the number of numbers.

And our problem states that n should be at least 2.

So we first generate a big random number using function rand.

Then we take it modulo 10, and

it gives us some random number between 0 and 9, and then we add 2.

And so we get a random number between 2 and 11.

Why is it so small?

Well, we first want both our solutions to work fast enough.

And also if we create a big random test, it will be hard for

us to debug it, so we start with some relatively small value of n.

We immediately output it on the screen, so that if we find some tests for

which our solution is wrong, we immediately see it on the screen.

6:07

After generating n, we should generate the array of numbers, a, itself.

So we iterate n times, and we add random numbers

from 0 to 99,999 to the end of array a.

So these are the numbers in the range which is allowed.

6:28

And then we also output all these numbers in one line,

separated by spaces and a newline character.

So by this time, we've already output the whole input test on the screen.

Now what we need to do is actually need to launch

both our solutions on this input test and get two results,

the result of the main solution and the result of the fast solution.

After that, we compare those two results.

If they are different, it means that at least one of the solutions was wrong.

So we output words Wrong answer on the screen, and we also output

the first result, a space, and the second result and a newline character.

After that, we break our loop.

We can notice that our while loop is a so-called infinite loop, but

we actually end it as soon as we find some test for which our solutions differ.

If we don't find the different sum test, we just output the word OK on the screen,

to denote that actually both solutions have already computed the answers,

but the answers are the same.

And then we continue.

So we continue our infinite loop, in the search of the test

that will save us, that we can use to debug our solution.

And we wrote that code just in front of all the code to read the numbers

from the input, to compute the answer, and to output it to the screen.

So we basically inserted this code in our regular program.

But instead of reading numbers from the input,

it will first try to find the test for which our two solutions differ.

And in the next video, we will launch this stress test to find a test in which our

solutions differ, debug our fast solution, and fix it.