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.

Â