Explore
For Enterprise
Join for Free
Log In

Blättern
Suche
Für Unternehmen
Anmelden
Kostenlose Teilnahme

Efficient Algorithm for Grouping Children

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (5,384 Bewertungen) | 170K Teilnehmer angemeldet

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). Do you have technical problems? Write to us: coursera@hse.ru

Lehrplan anzeigen

Kompetenzen, die Sie erwerben

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

Bewertungen

4.7 (5,384 Bewertungen)

5 stars
4,008 ratings
4 stars
1,094 ratings
3 stars
192 ratings
2 stars
39 ratings
1 star
51 ratings

MB

Mar 06, 2018

Cool course. Thank you! One suggestion about your book (Learning Algorithms Through Programming and Puzzle Solving): could you add some theory which would serve as a brief reminder before problems?

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

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.

Erhältlich bei Google Play

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

Community
Learners
Partners
Developers
Beta Testers
Translators

Verbinden
Blog
Facebook
LinkedIn
Twitter
Instagram
Youtube
Tech-Blog

Mehr
Nutzungsbedingungen/AGB
Datenschutz
Hilfe
Barrierefreiheit
Presse
Kontakt
Verzeichnis
Partnerunternehmen