Let us now summarize.

So as we've seen in many cases,

a greedy algorithm defines some greedy ordering in a natural sense.

For example, in the largest number,

what we've discovered is that it makes sense to first take larger digits.

In the money change, again,

we've realized that it makes sense to first take larger coins.

In the activity selection,

we've proved actually that the activity of

the segment with the minimum right end point is better in a sense.

And then the scalar product in a sense what we've also shown is that the element of B,

the larger it is the better.

And in many cases,

such a strategy can be also converted to a sorting algorithm which

sorts with respect to some implicit ordering that we have implicitly now in our solution.

So let me show you more compact solutions,

more compact code for the three problems considered previously.

In the largest number problem,

what we essentially would like to do is to arrange our digits in an increasing order.

So when this can be done just with one line of code.

So given a sequence of digits,

we first sort them.

So here we use the flac reverse in order to sort them not

in a decreasing order but in an increasing the.

And then we just concatenate all these digits.

For the money change problem,

what we would like to do is to first,

in a sense go in the decreasing order of denominations.

So we first would like to take as many coins with denomination 10,

then as many points of denomination five as many as possible.

And finally as many coins as needed of denomination one.

And this can be even done without sorting or without any loops because it is

easy to compute the number of coins of denomination 10 that needs to be taken.

This is just M divided by 10.

More precisely, is the integral part of this.

So we just divide M by 10 and this is the number of points of denomination 10.

Then what is left is the remainder of M divided by 10.

If we divide this by five,

this will give us the number of points of denomination five that is needed.

And this is actually always as a zero or one.

And finally if we take M,

if we take the remainder of M divided by five,

this will give us the number of coins of

denomination one that are needed in our optimum solution.

Finally, in the maximum scalar product problem,

what we've proved actually is that we need to multiply

the largest element of A with the largest element of B.

And what is left is essentially the same problem.

Then we would like to multiply

the second largest element of A with the second largest element of B.

And this gives rise to the following solution.

Let's just sort both sequences,

A and B and then multiply them point twice.

So multiply the first element of

the sort that A was the first element that was of sort of,

B the second element of A was the second element of B, and so on.

And again, this can be done just with a few lines of code.

For the activity selection problem,

we can do the following.

We first sort all our segments by the right end points.

This gives us a sorted sequence of segments.

Then we scan it from left to right and we keep repeating the following procedure.

We take the current segment into our solution and then we

scan the sequence from left to right

and to remove all the segments that are intersected by the current segment.

After we remove all the segments,

we actually continue doing the same thing.

We take the current segment into our solution and we

scan the sequence to remove all the segments that are intersected, and so on.

So we have such an order in mind and

usually what is also important for such an ordering is that it is transitive.

Then usually to prove that such an ordering gives a correct greedy algorithm,

what we need to prove is the following.

If we have some permutation of our objects and some two objects,

actually via [inaudible] ordering so we have an ordering

which is specified binary relation at most.

And if some element in our sequence is greater than the next element,

then if we swap these two elements that we can only improve our solution.

So once again, in many cases when we have

such an ordering at most and that is transitive,

it is enough just to sort the given object with respect for this ordering.

Finally, let me summarize what we've learned in this lesson.

So the greedy strategy usually constructs a solution piece by piece and that

this iteration is just naively select the most profitable piece of advice.

In many cases, this leads to very efficient and compact solutions.

This is an advantage of the greedy strategy.

The main disadvantage is that this strategy actually rarely works.

What is worse is that there are optimizational problems for

which greedy solution seems to be natural and correct but they are not correct in fact.

So remember to always prove the correctness of your greedy approach.