Largest Number

Loading...

From the course by University of California San Diego

Algorithmic Toolbox

3958 ratings

University of California San Diego

Algorithmic Toolbox

3958 ratings

Course 1 of 6 in the 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).

From the lesson

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

Meet the Instructors

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, I'm Michael Levin and together we will study Greedy Algorithms.

They are some of the simplest algorithms that exist and

they usually seem a pretty natural way to try solving a problem.

We will start with a few examples of problems that can be

solved by greedy algorithms, just to illustrate how they work.

And our very first problem is a problem about largest number.

And for this problem, you will probably be able to come up with a greedy algorithm

yourself, because that is really a very natural thing to do.

So imagine this situation.

You are trying to get a job at a company and you already had a few interviews, and

everything went well.

Now you have your final interview with the boss, and

he tells you that he will give you an offer.

But instead of negotiating your salary with you,

he will give you a few pieces of paper with digits written on them.

And your task will be to arrange those digits in a row, so

that when you read the number from left to right, that will be your salary.

So basically, you have a problem.

Given a few digits, to arrange them in the largest possible number.

And there are a few examples of such numbers on the slide.

So what do you think will be the correct answer to this problem?

And of course, the correct answer is 997531.

And it's pretty obvious that you should arrange numbers from the largest to

the smallest, from left to right.

But let's look at how the greedy algorithm does that.

So, the Greedy Strategy is start with a list of digits then

find the maximum digit in the list.

Append it to the number and remove it from the list.

And then repeat this process until there are no digits left in the list.

So on the next step we will find the largest digit, which is again 9.

We'll append it to the number to the right and remove it from the list.

Then we will find 7 as the largest digit appended to the right and

remove it from the list.

And then we'll continue with 5, 3, and 1.

And then we get the correct answer, 997531.

And in the next video, we will design an algorithm

to find the minimum number of refuels during a long journey by car.

We will see similarities between these two problems,

largest number problem and car refueling problem.

And we will define how greedy algorithms work in general.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play