Explore
For Enterprise
Join for Free
Log In

Browse
Search
For Enterprise
Log In
Join for Free

Problem Overview

Loading...

Algorithmic Toolbox

University of California San Diego

4.7 (5,387 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,387 ratings)

5 stars
4,008 ratings
4 stars
1,096 ratings
3 stars
193 ratings
2 stars
39 ratings
1 star
51 ratings

MB

Mar 06, 2018

Cool course. Thank you! One suggestion about your book (Learning Algorithms Through Programming and Puzzle Solving): could you add some theory which would serve as a brief reminder before problems?

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

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