Lec 13 | MIT 6.00 Introduction to Computer Science and Programming, Fall 2008

[OctopusMagnetism]

Invent Team Recursive "fib/tabs" if you must, but do not use them to break the law or compromise citizen safety. info distribution can be harmful to many more people than the Stealee.

[frankfurt28]

This guy, seems he is not familiar with DP, and he is trying to explain something he doesn't quite well understand... He firstly forgets to mention the difference between DP and divide and conquer techniques, he doesn't mention NP complete problems, and he makes an explanation of the kanpsack problem so obscure, that is so boring to follow. Although he mentions fibonacci at the beginning he fails to say that in DP also you got to solve the problem at a point based on solutions so far computed.

[Slampropp]

Python facilitates memoization beutifully via default argument values;

def fib(n, memo={0:0, 1:1}):

This is much cleaner than his method of initializing the memo in a wrapper function, and has the added benefit (possibly) that the memo is global, i.e., the memoized values are retained between top-level calls to fib.

[havokca]

The actual fibonacci sequence is defined as 0,1,1,2,3,5,8,13, etc... 0 and 1 are the first two numbers and every subsequent number is the sum of the previous two.

Based on his definitions (which are in the code and are very obvious in fastfib) he's omitting the leading 0 (which is wrong... but the fact that it's wrong is irrelevant) and he's starting his count at 0. So fib(0) = 1, fib(1) = 1, fib(2) = 2, fib(3) = 3, fib(4) = 5, fib(5) = 8 and fib(6) = 13

It threw me a bit at first too.

[kharrell904]

So what is the official 6th fibonacci number? If you use the Binet method, isn't it 6? I've looked at a couple different sites and most say 6. I ran across a site with some interesting behaviors of the series. One behavior is that every 3rd number is divisible by 2 and every 6th number is divisible by 8. 8 fits and 13 doesn't. Even if you use the recursive method by hand with seed values 0 and 1, F(6) = 8, right?

[agapitoflores001]

This is completely awesome. More videos please.

[codefusions]

Thumbs up if you thought of Fast Fap when he said Fast Fib.

They seem to like to use insinuative names for their functions in this course.

[assbigasyou]

which language is he using??????????

[loko95ftp]

@assbigasyou

PYthon 

[assbigasyou]

@loko95ftp thanks.. i wanna have to get started with this language after i expertise on Java ...

[adkatrit]

There is a direct formula for the nth fibonacci using Binet's formula with the golden ratio and phi:

(1/sqrt(5))((((1+sqrt(5))/2)^n­)-((1-sqrt(5))/2)^n)

BAM nth fibonacci with no iteration at all. just make sure you set your precision high enough.

[xzminx]

@adkatrit Its not with no iteration, you still have to calculate the golden ratio to the power of n, which will take O(log n) time at least.

[adkatrit]

@xzminx good point. It will still be more efficient than memoized recursion correct?

[xzminx]

@adkatrit depends on what you use. you need to have high precision data format like BigDecimal which will slow things even further. Also depends what u use it for, and how often, and is there a highest n that you will ever need fib(n).

Here's what I would do:

1. if i need fib(n) rarely: do linear calculation starting from 0 and 1 towards N

2. if i need it often: recursion with memoization, but recursive call shoul be fib(n) = fib(n-2) + fib(n-1), because fib(n-1) uses fib(n-2) to calculate.

[mi1ha]

By definition, the first two Fibonacci numbers are 0 and 1, and each subsequent number is the sum of the previous two.

fib 0,1,1,2,3,5 so fib(6) = 5 and fib(0) = 0

but even if we omit the initial 0, instead beginning the sequence with two 1s.

1,1,2,3,5,8

fib(6) is 8

[Diego18tv]

fib(0) = 0 it was right at the beginning

[elhlaby]

Did MIT switch to Python? What programming language they used to teach?

[Nisstyre56]

@elhlaby Scheme dialect of Lisp

[coolguy6075]

It's actually the 31st Fibonacci, great stuff :)

[easter10]

sweet lectures :]