Explore
For Enterprise
Join for Free
Log In

Kunst und Geisteswissenschaften
Wirtschaft
Informatik
Datenverarbeitung
Informationstechnologie
Gesundheit
Mathematik und Logik
Persönliche Entwicklung
Physik und Ingenieurwesen
Sozialwissenschaften
Sprachen lernen
Abschlüsse
Zertifikate

Alle Bereiche erkunden

Blättern
Suche
Für Unternehmen
Anmelden
Kostenlose Teilnahme

Efficient Algorithm for Grouping Children

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (4,765 ratings) | 150K Students Enrolled

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

Bewertungen

4.7 (4,765 ratings)

5 stars
3,562 ratings
4 stars
958 ratings
3 stars
169 ratings
2 stars
35 ratings
1 star
41 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

AG

Feb 19, 2018

best course for clearing basics of algorithms as well as learning by doing and blow your mind by thinking hard from different prospectives to get desired solutions of programming assignments ...

Aus der Unterrichtseinheit

Greedy Algorithms

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.

Celebration Party Problem6:57

Efficient Algorithm for Grouping Children5:26

Analysis and Implementation of the Efficient Algorithm5:25

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.

Durchsuchen Sie unseren Katalog

Melden Sie sich kostenlos an und erhalten Sie individuelle Empfehlungen, Aktualisierungen und Angebote.

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

Coursera
Info
Leitung
Jobs
Katalog
Zertifikate
MasterTrack™ Certificates
Abschlüsse
Für Unternehmen
Für Regierungen

Community
Learners
Partners
Developers
Beta Testers
Translators

Verbinden
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Tech-Blog

mehr
Bedingungen
Datenschutz
Hilfe
Zugänglichkeit
Presse
Kontakt
Verzeichnis
Partnerunternehmen