Explore
For Enterprise
Join for Free
Log In

Browse
Search
For Enterprise
Log In
Join for Free

Largest Number

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (5,261 ratings) | 160K Students Enrolled

Course 1 of 6 in the Data Structures and Algorithms Specialization

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

Skills You'll Learn

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

Reviews

4.7 (5,261 ratings)

5 stars
3,917 ratings
4 stars
1,068 ratings
3 stars
188 ratings
2 stars
38 ratings
1 star
50 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

Aug 06, 2019

Thanks for the course, it was instructive! I like that some problems require implementing algorithms discussed in lectures, while others are quite challenging and are very satisfying to solve :)

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

Taught By

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

Transcript

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.

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government
For Campus

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates