Problem Overview

Loading...

From the course by University of California San Diego

Algorithmic Toolbox

4473 ratings

University of California San Diego

Algorithmic Toolbox

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

Today we're going to start talk about Fibonacci Numbers and

algorithms to compute them.

In particular, in this lecture we're just going to introduce the sequence of

the Fibonacci numbers and talk a little bit about their properties.

So to begin with the Fibonacci numbers is a fairly classically studied

sequence of natural numbers.

The 0th element of the sequence is 0.

The first element is 1.

And from thereon, each element is the sum of the previous two.

So 0 and 1 is 1.

1 + 1 is 2.

1 + 2 is 3.

2 + 3 is 5.

And the sequence continues, 8, 13, 21, 34, and so on.

So it's a nice sequence of numbers defined by some pretty simple recursive

rule and it's interesting for a number of reasons.

It has some interesting number theoretic properties, but originally this sequence

was developed by an Italian mathematician as a mathematical model.

And it's a little bit weird.

You might try and wonder what sorts of things this could be a model for.

Well, it turns out that, originally,

this was used as sort of a mathematical model for rabbit populations.

There was some idea that if you had a pair of rabbits,

it would take them one generation to mature and every generation thereafter,

they'd produce a pair of offspring.

And if you work out what this means, then you find out the Fibonacci numbers,

tell you how many pairs of rabbits you have after n generations.

Now, because rabbits are known for reproducing rather quickly, you might

assume that the sequence therefore grows quickly, and in fact it does.

It's not hard to show that the nth Fibonacci number is at

least 2 to the n over 2 for all n at least 6.

And the proof can be made by induction.

You prove this directly for n 6 or

7 just by computing the numbers and showing that they're big enough.

And after that point, Fn is the sum of Fn-1 and Fn-2.

By the inductive hypothesis, you bound that below and

do a little bit of arithmetic.

And it's bounded below by 2 to the n/2.

So that completes the proof.

In fact, with a little bit more work you can actually get a formula for

the nth Fibonacci number as roughly 1 point square root of 5 over 2 to the n.

These things grow exponentially quickly.

And to sort of drive that home a little bit more, we can look at some examples.

The 20th Fibonacci number is 6765.

The 50th Fibonacci number is approximately 12 billion.

The 100th Fibonacci number is much, much bigger than that.

And the 500th Fibonacci number is this monster with something like a 100

digits to it.

So these numbers do get rather large quite quickly.

So the problem that we're going to be looking into for

the next couple of lectures is, how do you compute Fibonacci?

So, if you want to use them to model rabbit populations or

because of some number theoretic interest.

We'd like an algorithm that as input takes a non negative integer n and

returns the nth Fibonacci number.

And we're going to talk about how you go about doing this.

So, come back next lecture and we'll talk about that.

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