Until now, we're ready to check our codes ourselves.

Let's talk about what's in the computer to do this work.

But first, let's talk about invariants.

In these codes, we have read our counting loop invariants.

Now, we will generalize this concept.

Invariant is a correct statement about data you're working with.

You don't need to come up with invariants specially.

They always arise naturally.

As a loop invariant,

every invariant corresponds to someplace in your code.

Consider the first example.

Here we have an array of integers.

We simply iterate over it and each time we find a negative element,

we change its sign to the opposite side.

We also compute sum of all elements in array after applying this operation.

In the int, we print the sum.

It is obvious that after the loop,

every element in the array will be non-negative.

That's why we can define the invariant,

which you can see on the slide.

Note that we can't put this invariant before the loop.

Consider the second example.

Here we also have an array of integers.

All we do is read in it,

sort in it, and print in it.

Suppose that functions with the appropriate names do this.

And then we have an obvious invariant after sorting.

When the array is sorted,

all elements in it are in non-decreasing order.

So for every i from zero to n minus two,

ith element of the array must be not greater than i plus one element of the array.

It is reasonable to expect that in the way can code all invariants must be satisfied.

So we can check all of them and if we will find a non-satisfied invariant,

we can conclude that there is a bug near by this invariant.

But checking invariants in two previous examples by hand is a big and unreasonable way.

So let's entrust this work to a computer.

There is one special function in each of the main programming languages.

It is usually called "Assert".

It takes an expression as an argument,

computes it, and throws the an error if the result is false.

For example, the expression two is less than three is always true.

So if we pass it to this function,

it will do nothing,

but the expression two plus two equals five, is false.

Surpassing each of this function leads to error.

With asserts, we can automatically check any calculable expressions,

so we can automatically check invariants.

When we use asserts,

our code is actually checked twice by testing and by checking invariants.

Now a few words about Java.

You can assume that in every language,

an assert behaves like a conditional operator.

If a statement is not true through an exception, certainly,

we use asserts for simplicity,

but in Java assert are checked only with the compilation

key -ea, that means "Enableassertions."

You can use this key on your computer,

but on the server the compilation keys may be different.

That's why on Java,

it's recommended to use the mechanism of exceptions.

Let's see how we can use asserts in our examples.

The first example, we expect that after the first loop of elements will be non-negative.

So we can iterate over all elements and check this assertion for every element.

With the current example,

we expect that after sorting,

all elements will be in non-decreasing order.

So we can iterate over all pairs of

neighboring elements and check this assertion for them.

As it was said earlier, if some assertion fails,

it usually means that there is a bug in the code before this assertion.

Can see that in more complicated situation.

You'll know that your code doesn't work.

For example, you sent it to the testing system and they are saved a verdict wrong

answer and you don't know any test on which your code works incorrectly.

In this case, you can add asserts to your codes

in the same way and just send it to the testing system.

And if you see that your code crash with a runtime error on some test,

it can mean that some assertions have failed.

You can find them one by one.

Command out all asserts except the first,

command out all asserts except the second, and so on.

Unfortunately, in attaining an error doesn't always mean failing of assertion.

There are other cases in which an error can be attained.

Array indexes out of bounds division by zero,

infinite recursion, and so on.

So you should be careful with this method of finding bugs.