In this video, we're going to show how to

prove that a particular greedy algorithm works correctly.

That is, it always returns an optimal solution.

So recall that at every step,

a greedy algorithm chooses the most profitable piece of a solution.

So in a sense,

what we're doing at this point is that we are restricting our search space.

So for example, in the largest number when

we say let's start our number with the largest digit,

we essentially say, instead of considering all possible numbers composable of our digits,

let's consider only those that start with the largest digit.

In the money change problem,

when we say let's take the largest coin that does not exceed the given amount of money,

we say instead of considering all possible ways of changing the given amount of money,

let's consider only those that contain this largest coin.

So, essentially, to prove that

such a greedy algorithm works correctly what we need to show

is that the restricted search space contains an optimum solution.

In turn, to prove that the restricted search space contains an optimal solution,

one might follow the following template or the following pattern.

So start with some optimum solution.

So, if it belongs to the search space, then we are done.

Then there is nothing to prove.

If on the other hand it does not belong to the restricted search space,

then what we need to do is to tweak it a little bit so that it is still

optimum and at the same time it belongs to the restricted search space.

Let me illustrate this with

proving the correctness of the two problems considered before.

So formally, what we need to show for the largest number problem is the following.

In this case, the solution is actually unique because we suggest the largest number,

so we will prove that not just that they exist in optimum solution

in the search space but that the solution lies in the restricted search space.

Namely, we will show that the largest number actually starts with the largest digit,

and it is not difficult to show.

So I assume for the contrary that the largest number starts not with the largest digit,

but with some other digit, dj.

So, dj is not the largest digit and the i is the largest digit is

somewhere in the middle of our largest number.

Then just by swapping these two digits,

of course we get a larger number which contradicts there is

a fact that our initial number was indeed the optimum one.

So, this was not difficult.

Let's proceed to the money change problem.

In this case, the statement is the following.

For any positive integer m,

there is an optimum way of changing m using a coin which is the largest coin

that does not exceed m. So we prove it by considering a few cases.

So first of all,

let's denote the largest coin out of one,

five and 10 which does not exceed m by

d. So what we need to show is that there always exist

san optimum way of changing m using the coin of

denomination d. So now let's consider three cases.

If m is smaller than five then d is equal to one.

So one is the largest denomination that does not exceed m in this case.

So what we need to show is that,

the existing optimum way of changing m using coin of denomination one,

but this is easy since m is at most five,

we can only use coins of denomination one.

So essentially, there is nothing to prove in this case.

The second case is when m is at least five and smaller than 10.

So what we need to show is that there exists an optimum way of

changing m using the coin of denomination five.

In this case, we can only use coins of denomination one and five.

So, if we do not use a coin of denomination five,

then all the coins should be of denomination one.

And since m is at least five,

there should be at least five such coins.

And we can replace them by a coin of denomination five

and we will improve our solution by doing this.

And this shows that of course,

actually in any optimum way of changing m

in this case there must be a coin of denomination five.

Finally, I assume in this case that m is at least 10.

What we need to show is that there

exists an optimum solution that contains a coin of denomination 10.

This in turn can be shown by considering a few sub-cases.

So first of all,

consider some optimum solution.

If it contains a coin of denomination 10 then we are done,

there is nothing to prove.

So, I assume that there is no coin of denomination 10.

Then consider a few sub-cases.

If it contains for example,

at least two coins of denomination five,

then we can replace them by one coin of denomination 10.

This will improve the solution. If it contains just one coin of denomination five,

then it must contain at least five coins of denomination one,

just because m is at least 10 and we can't

replace all these coins with one coin of denomination 10.

Finally, if there are no coins of denomination five,

then there should be at least 10 coins of denomination one.

And all of them can be replaced with just a single coin with denomination 10,

which finally proves our lemma.

Let me finally also mention that it is exactly the last step

of this proof where it would break four denominations one, four and six.

So, recall that for such denominations,

the greedy algorithm actually doesn't work because it will

change the amount eight with coins six,

one and one, while the optimum way of changing this

is by using just two coins of denomination four.