Main Ingredients of Greedy Algorithms

Loading...

En provenance du cours de University of California San Diego

Algorithmic Toolbox

4100 notes

University of California San Diego

Algorithmic Toolbox

4100 notes

Cours 1 sur 6 dans Specialization Data Structures and Algorithms

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).

À partir de la leçon

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.

Largest Number2:42

Car Fueling7:27

Car Fueling - Implementation and Analysis9:14

Main Ingredients of Greedy Algorithms2:40

Rencontrer les enseignants

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

Hi. In this video,

we will briefly review the main ingredients of greedy algorithms and

the first of them is reduction to a subproblem.

Basically, when you have some problem, you make some first move and

thus reduce your problem to a similar problem, but which is smaller.

For example, you have fewer digits left or fewer gas stations left in front of

you and this similar problem, which is smaller is called a subproblem.

Another key ingredient is a safe move and

the move is called safe if it is consistent with some optimal solution.

In other words, if there exists some optimal solution in which the first

move is the same as your move, then your move is called a safe move and

not all first moves are actually safe.

For example,

to go until there's no fuel is not a safe move in the problem about car fueling.

And often, greedy moves are also not safe, for example,

to get to the closest gas station and refuel at it is not a safe

move while to get to the farthest gas station and refuel there is a safe move.

Now the general strategy of solving a problem goes like this.

First, you analyze the problem and you come up with some greedy choice and

then the key thing is to prove that this greedy choice is a safe move and

you really have to prove it.

Because, otherwise, you can come up with some greedy choice and

then come up with a greedy algorithm and then even implement it and test it and

try to submit it in the system.

Only to learn that the algorithm is incorrect,

because the first move is actually not a safe move and there are cases in which

this first move is not consistent with any optimal solution.

And in that case, we will have to invent a new solution and

implement it from scratch.

All the work you've done before will be useless.

So please prove your algorithms and prove that the first move is a safe move.

When you prove that, you reduce a problem to a subproblem.

And hopefully, that is a similar problem, problem of a same kind and

then you start solving this subproblem the same way.

You make your greedy choice and you reduce it to subproblem, and

you iterate until there are no problems left or until your problem is so

simple that you can just solve it right away.

And in the next lessons,

we will apply greedy algorithms to solve more difficult problems.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play