Hello everybody, welcome back.

In this video, we're going to start studying Greedy Algorithms.

So, this is a natural type of natural class of algorithms.

They build the solution piece by piece.

And at each step, they select the most profitable piece of the solution.

Let's illustrate this strategy with Two-Toy problems.

The first one is the so-called largest number problem.

The input to this problem consists of an integers of N single digit integers D0,

D1 and so on, Dn minus one.

What we would like to do is to compose the largest possible number out of these digits.

For example, for the input two, three, nine, three,

two, the largest number composable out of these digits is 93322.

There is a natural idea for solving this problem.

Of course, we would like to start our number with the largest possible digit.

This is just because we know that all possible such numbers have the same length.

So, it is just natural to start with the largest possible digit.

Again what is left is essentially the same problem.

So, for our Toy example,

we would like to start with the number

nine and then what is left are digits three, three,

two, two and we would like to arrange them somehow to get the largest possible number.

And this leads us to the following code.

So, we are given the sequence of digits,

we first declare the variable result

which is just an empty array in the beginning and then we keep repeating the following.

We select the largest digit,

we remove it from the sequence of digits,

and we append it to the least result.

Finally, in the last line of our code,

we just join all our digits by

empty spaces and we get a string consisting of

all the digits in the same order as in the least result.

The running time of this code is N squared

just because there are at most N iterations of the Y loop.

And inside each iteration we need to find the maximum,

which actually amounts to scanning the current list of digits.

And again, it takes a linear amount of work.

The next problem is so-called money change problem.

In this case, we are given a non-negative integer M,

so some amount of money M. And what we would like to do is to change M with

the least possible number of coins with denominations one, five, and 10.

For example, for the input when M is equal to 28,

the result should be equal to six.

Indeed 28 can be represented as

10 plus 10 plus five plus one plus one and plus one, so six points.

Again, there is a natural gradient strategy for

this problem and that it actually used by cashiers all over the world.

So, to change the given amount M with

the least number of coins just keep repeating the following procedure.

Just first take the coin with the largest denominations that does not

exceed M. Then take this coin,

subtract it's denomination from M and repeat.

This gives us the following code.

So, in this code the parameters taken to the procedure M

and the set of coins that there's a list of denominations of coins.

And then we proceed as follows.

First, we declare as a variable result,

this is just an empty array in the beginning.

Then while M is empty,

we do the following.

In the fifth line,

we find the maximum denominations that does not exceed

M. Then we subtract it from M and we append this denomination to the result.

And finally, we just join all these coins by the plus sign.

So, for example for the input 28,

again this procedure will return 10 plus 10 plus five plus one plus one plus one.

The running time of this procedure is M times the size of coins.

And the reason is simple.

So, the right most M iterations because at

every iteration of the Y loop will decrease M at least by one.

And at every iteration,

we need to find the maximum denomination of the coins,

so we need to find a maximum in an array of size coins.

So, this definitely can be done in time bigger of coins.

So, now when we've seen two examples let's analyse them.

First of all, we know we've seen that it gives

us very compact solutions and they are also efficient solutions.

At the same time,

it is more of a coincidence that these solutions actually work correctly in all cases.

To see these, let me mention the following two interesting facts.

So, if instead of considering digits in our problem largest number

we consider arbitrary positive integers,

then the correspondent algorithms might fail.

For example, if we consider the input consisting of two numbers two and 21,

then our algorithm will first put 21 and

then append two just because 21 is larger than two.

This will give us the number 212.

But this is a sub-optimal result.

Because in this case,

it is much better to put two into the beginning and then to append 21 to them

because this will give us the number 221 instead of 212.

Similarly, if we consider other denominations of coins,

for example, denominations one,

four, and six, our greedy algorithm might

produce a sub-optimal result as illustrated by the following example.

If we ask our greedy strategy to change eight,

it will return six plus one plus one,

that is three coins instead of just two coins four plus four.

So, a priori, indeed there should be no reason why

the naive greedy strategy produces an optimal solution.

So, it turns out that for

our largest number problem and for greedy change with denominations one,

five and 10, the greedy strategy works correctly.

But it is important to always prove the correctness of greedy algorithms.

And this is exactly what we're going to do in the next video.