Efficient Algorithm

Loading...

From the course by University of California San Diego

Algorithmic Toolbox

3510 ratings

University of California San Diego

Algorithmic Toolbox

3510 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

Algorithmic Warm-up

In this module you will learn that programs based on efficient algorithms can solve the same problem billions of times faster than programs based on naïve algorithms. You will learn how to estimate the running time and memory of an algorithm without even implementing it. Armed with this knowledge, you will be able to compare various algorithms, select the most efficient ones, and finally implement them as our programming challenges!

Problem Overview3:20

Naive Algorithm5:36

Efficient Algorithm3:56

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

Hello, everybody, welcome back.

We're still talking about algorithms to compute Fibonacci numbers.

And in this lecture,

we're going to see how to actually compute them reasonably efficiently.

So, as you'll recall, the Fibonacci numbers was the sequence zero,

then one, then a bunch of elements, each of which is the sum of the previous two.

We had a very nice algorithm for them last time, which unfortunately was very, very

slow, even to compute the 100th Fibonacci number say. So we'd like to do better.

And maybe you need some idea for this new algorithm.

And one way to think about it is what do you do when you compute them by hand.

And in particular,

suppose we want to write down a list of all the Fibonacci numbers.

Well, there's sort of an obvious way to do this.

You start off by writing zero and one because those are the first two.

The next one going to be zero plus one, which is one.

The next one is one plus one which is two, and one plus two, which is three,

and two plus three, which is five.

And at each step, all I need to do is look at the last two elements of the list and

add them together.

So, three and five are the last two, I add them together, and I get eight.

And, this way, since I have all of the previous numbers written down,

I don't need to do these recursive calls that I was making in the last lecture,

that were really slowing us down.

So, let's see how this algorithm works.

What I need to do is I need to create an array in order to store

all the numbers in this list that I'm writing down.

The zeroth element of the array gets set to zero,

the first element gets set to one, that's to set our initial conditions.

Then as i runs from two to n, we need to set the ith element to be the sum of the i

minus first and i minus second elements.

That correctly computes the ith Fibonacci number.

Then, at the end of the day, once I've filled out the entire list,

I'm going to return the last element after that.

So, now we can say, this is another algorithm,

it should work just as well, but, how fast is it?

Well, how many lines of code did you use?

There are three lines of code at the beginning, and

there's a return statement at the end, so that's four lines of code.

Next up we have this for statement that we run through n minus one times,

and each time we have to execute two lines of code.

So adding everything together we find out that t of n is something like 2n plus two.

So if we wanted to run this program on input n equals 100,

it would take us about 202 lines of code to run it.

And 202 is actually a pretty small number even on a very modest computer these days.

So essentially, this thing is going to be trivial to compute the 100th or

the 1,000th or the 10,000th Fibonacci number on any reasonable computer.

And this is much better than the results that we were seeing in the last lecture.

So in summary, what we've done in this last

few lectures, we've talked about the Fibonacci numbers, we've introduced them.

We've come up with this naive algorithm,

this very simple algorithm that goes directly from the definition, that

unfortunately takes thousands of years, even on very small examples to finish.

On the other hand, the algorithm we just saw is much better, it's incredibly fast

even on fairly large inputs and it works quite well in practice.

And so, the moral of this story,

the thing to really keep in mind is that in this case and

in many, many others the right algorithm makes all the difference in the world.

It's the difference between an algorithm that will

never finish in your entire lifetime and one that finishes in the blink of an eye.

And so, that's the story with Fibonacci numbers.

Next lecture we're going to talk about a very similar story that comes with

computing greatest common divisors.

So I hope you come back for that.

Until then, farewell.

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.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play