Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
Imperial College London
Try out Imperial's GMPH degree with their new open courses
Get a sample of the topics covered in the fully online Global Master of Public Health degree
University of Michigan
Earn a master's in data science from Michigan
Launch your data science career with a degree from one of the world’s best schools of information
Degrees
Certificates

Explore all of Coursera

Browse
Top Courses
For Enterprise
Log In
Join for Free

Problem Overview

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (5,488 ratings) | 170K 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,488 ratings)

5 stars
4,077 ratings
4 stars
1,121 ratings
3 stars
197 ratings
2 stars
40 ratings
1 star
53 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

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

Taught By

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

Transcript

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.

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