Loading...

Efficient Algorithm for Grouping Children

Course video 24 of 60

In this module you will learn about seemingly naïve yet powerful class of algorithms called greedy algorithms. After you will learn the key idea behind the greedy algorithms, you may feel that they represent the algorithmic Swiss army knife that can be applied to solve nearly all programming challenges in this course. But be warned: with a few exceptions that we will cover, this intuitive idea rarely works in practice! For this reason, it is important to prove that a greedy algorithm always produces an optimal solution before using this algorithm. In the end of this module, we will test your intuition and taste for greedy algorithms by offering several programming challenges.

Algorithmic Toolbox

University of California San Diego

Kurs 1 von 6 in Datenstrukturen und Algorithmen Spezialisierung

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

Lehrplan anzeigen

Skills You'll Learn

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Unterrichtet von

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Skript

Hi, in this lesson you will learn how to solve the problem of

organizing children into groups more efficiently.

Most specifically, we will come up with a polynomial time algorithm for

this problem as opposed to the exponential type algorithm from the previous lesson.

But in order to do this, we first need to do a very important thing

that you should probably do every time before solving an algorithmic problem.

You should reformulate it in mathematical terms.

For example,

in this problem we will consider points on the line instead of children.

For example, if we have a child of age three and a half years we will instead

consider a point on the line with coordinate 3.5 and if we have another

child of age 6, we will instead consider a point with coordinate 6 on the line.

Now, what do groups of children correspond to?

If we have a group of children, it consists of several children and

several points on the line correspond to this group and the fact that the age

of any two children in the group differs by at most one, means that there exists

a segment of length one on this line that contains all those points.

Now the goal becomes to select the minimum possible number of segments

of length one, such that those segments cover all the points.

Then, if we have such segments,

we can just take all the points from that segment in the same group,

and any two children in the group who differ by, at most, one year.

Now let's look at an example.

We have a line with a few points on it and

we want to cover all the points with segments of length one.

Here is one example of such covering.

All the segments on the picture are of the same length and

we consider that this is length one of this line.

This is not the optimal solution because below there is another example of covering

and we have only three segments and they still cover all the points.

Now we want to find a way to find the minimum possible number of segments to

cover all the points in any configuration.

We want to do that using greedy algorithm and you probably remember

from the previous lessons that to come up with a greedy algorithm, you need to

do a greedy choice and to prove that this greedy choice is a safe move.

I state that in this problem, safe move is to cover the leftmost point

with a segment of length one which starts or has left end in this point.

To prove that this is really a safe move, we need to prove that there exists an

optimal solution with the minimum possible number of

unit length segments such that one of the segments

has its left end in the leftmost point.

Let's prove that.

To do that, let's consider any optimal solution of a given

problem with a given point.

Let's consider the leftmost point colored in green.

It is covered by some segment.

Colored in red.

Now, let's move this red segment to the right until it's left

end is in this leftmost point.

I say that we didn't miss any of the points in the process, because this green

point is the leftmost point so there are no points to the left from it and

while we are moving the segment to the right, we didn't miss any of the points.

It means that what we have now is still a correct covering because

all of the points are still covered and the number of segments in this covering is

the same as in some optimal solution from which we started and

that means that it is also an optimal covering.

So we have just found an optimal solution

in which there is a segment which starts in the leftmost point.

So, we proved that

covering the leftmost point with a segment which starts in it is a safe move.

Now that we have a safe move, let's consider what happens after it.

We have the leftmost point covered, and also maybe some other points covered.

So we don't need to consider these points anymore.

We are not interested in them and we need to cover all the other points with

the minimum possible number of unit length segments.

So this is the same kind of problem which we started with, so

this is a subproblem.

Basically it means that we have a greedy algorithm.

First, make a safe move. Add a segment to the solution

with the left hand starting in the leftmost point.

Then remove all the points which are already covered by the segment

from the set and if there are still points left, repeat the process and

repeat this process until there are no points left in the set.

Über Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

Coursera arbeitet mit erstklassigen Universitäten und Organisationen zusammen, um Online-Kurse anzubieten und dadurch universellen Zugriff auf die weltweit beste Ausbildung zu ermöglichen.

© 2019 Coursera Inc. Alle Rechte vorbehalten.

Aus dem App Store herunterladen

Erhältlich bei Google Play