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

Lecture 13: Dynamic programming: overlapping subproblems, optimal substructure

Instructors: Prof. Eric Grimson, Prof. John Guttag

View the complete course at: http://ocw.mit.edu/6-00F08

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

Category:

Education

Tags:

• computer
• programming
• Python
• science
• computation
• problem
• solving
• recursion
• binary
• search
• classes
• inheritance
• libraries
• algorithms
• optimization
• problems
• modules
• simulation
• big-O-notation
• control
• flow
• exceptions
• building
• computational
• models
• software
• engineering

[easter10]

sweet lectures :]

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

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

[Nisstyre56]

@elhlaby Scheme dialect of Lisp

[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]

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

[loko95ftp]

@assbigasyou

PYthon