2. Optimization Problems

MIT 6.0002 Introduction to Computational Thinking and Data Science, Fall 2016
View the complete course: ocw.mit.edu/6-0...
Instructor: John Guttag
Prof. Guttag explains dynamic programming and shows some applications of the process.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@ElVerdaderoAbejorro]

The part about the origin of the name "dynamic programming" was hilarious! \o/ Thank you, professor, for going the extra mile and researching that for us. =D

[@jacobsonokoro2173]

One of the courses that I can say changed my life.

[@beoptimistic5853]

kzbin.info/www/bejne/joGmmHqKbqefqLM 💐.

[@leixun]

*My takeaways:* 1. Pros and Cons in greedy algorithm 1:05 2. Brute force algorithm implementation using search tree 2:08 - Brute force algorithm is not efficient to compute, but dynamic programming can help with it 23:30

[@aidenigelson9826]

Can you please explain to me how the recursive procedure works in maxval? I don't fully understand withval and withoutval and the withtak and without take.

[@amolizm]

bro is not enjoying the show

[@monffy58]

I watched this course after 6.006, I have to say Dr John's course is much easier to understand, this one has a lot of vivid examples. Maybe I'm not smart enough to follow 6.006 and 6.046 well, but this course is really detailed and good for most people to learn.

[@MrRandompersondude1]

This is an introductory course, whereas in introduction to Algorithms, the word introduction is somewhat misleading because it is intended for students that have some pre-existing experience in CS.

[@JamesJon1187]

I love how he always looks like he's possibly trying to suppress a laugh. What an awesome guy!!

[@pfever]

My favorite instructor for this course!

[@hdsmsmart]

Thanks MIT OCW and Dr John Guttag !!!

[@ramind10001]

I believe Eric Grimson, Ana Bell and JohnGuttag are one of the best lecturers at MIT.

[@studywithjosh5109]

Ramin Dehghan some of*

[@marietaazatyan1044]

Gilbert Strang

[@dearharshmehra]

Same feeling bro But that may be because you only took 60001 and this course 😁

[@dharmiknaik1772]

How about prof. Eric Demaine?

[@pauloflores637]

Awesome! I've got really suprised with fast fibonacci's speed. Great job!

[@Pasora]

At 33:02 on line 129 of the code, it should return n instead of 1 because if it returns 1 you will be calculating one step more than what you asked for. fib(5) should return 5 but the code will return you 8 which is fib(6).

[@NazriB]

Lies again? Oil Petrol

[@SinCityGT3]

Great lecture! Thank you for uploading these. I don't agree at all with using try/except though. The Professors reason was that it's fewer lines of code... but it's actually more. This is much easier to read and looks better... if n in memo: return memo[n] memo[n] = fib(n-1, memo) + fib(n-2, memo) return memo[n]

[@akshay.m10]

python programmers have a practice called "Its easier to ask forgiveness than permission" which means its easier to write try/except rather than writing C/C++ style if-else checks. So follow along

[@SinCityGT3]

Thanks for pointing that out. I looked into it. For others following along, this is done because if you say, "if n in memo return memo[n]" the item has to be looked up twice in the dictionary. I'm hesitant to follow along blindly with their style though, they are using getters and setters.

[@atlantis_expedition_member4747]

I'm with you on this one. To me, the python practice "akshay m" referred to does not have anything to do with this. This to my eyes, is uglier than the if statement method. Also, looking up a dictionary is a constant operation isn't it? So no harm in doing it as much as I like.

[@Elite7555]

@@akshay.m10 The thing is, he commits two sins: he uses Exceptions as normal part of the control flow, and then he even returns from the `except` clause, both of which are terrible code smell, regardless of programming language. I am a great fan of these lectures, but this is a terrible way to teach coding. He should use the `dict.get()` method, which returns `None`. He may think his solution to be "cleaner", but it is also slower. Exceptions are expensive.

[@manojnirmal9294]

Wonderful lecture and I learned a lot. In the accompanying Python code the lists for values and calories are missing an element. They have 8 elements each while the names list has 9 (See 15:03).

[@ArunKumar-yb2jn]

This was identified by many commentators in Lecture 1 as well. It's a mistake.

[@letitrot9547]

Thank you! I'm glad I can take this course

[@HibsMax]

A little bit late to the party, but at 6:36 it seems like the calorie values are messed up. If we're using the same code as before, beer should be 154 instead of 145. Also, Beer+Pizza+Burger cannot be the same as Beer+Pizza, but they both have 766 calories. I think it should be: 766, 412*, 508, 154*, 612, 258, 354, 0 (* = wrong). The answer should be Beer and Burger.

[@notagain3732]

Im glad i found this

[@nikitasid4947]

Correction (6 years after taking the course i have a correction!) regarding mutable arguments in the function's signature (31:44) - don't do that. Well known problem in Python, google for more info.

[@sarthakbindal7660]

But the course was taught in Fall 2016 :p. Which course were you talking about ?..

[@sithembelogabela1271]

@@sarthakbindal7660 probably same course different year.

[@LaughingShinoo]

It’s not a “problem in Python”. It’s expected behavior, which happens to be unknown for most people. Also, in this specific example it doesn’t hurt, at most it’ll be faster across re-executions..

[@akbarrauf2741]

thanks,mit

[@duanas6409]

In case you don't have the math background, the number of nodes is 2^(n+1)-1 (as @kev92 says) and you get it by using the geometric progression formula and adjusting the indexes en.wikipedia.org/wiki/Geometric_progression#Derivation

[@shobhamourya8396]

@21:00 For reproducible random numbers seed(int) function is used in R

[@aidenigelson9826]

Can someone please explain the recursive procedure in maxval? Especially in the withVal and withtoTake and the opposites of the two? How is it actually exploring the tree? When does it check between withVal and withoutVal

[@velzer9340]

13:35 - withVal and withoutVal appear only in case when it isn't obvious what branch should we choose. Line 69: let's see what is the best achievable result if item X is taken. We call our function with updated list toConsider (without item X) and avail (restriction) decreased by the cost of item X. Respectively, for withoutVal. Eventually, toConsider list will be empty, and the function will return (0, ()). That corresponds to a decision made in a leaf, there are no alternatives. Knowing that the program can determine what decision to make in the last series of nods above leaves. It gives results to the upper level and so on. My explanation is very messy, sorry. Line 75: compare consequences of taking and not taking (withVal and withoutVal) and return the best. The function returns the best possible value and a tuple of taken items for given items and a restriction. Please, ask questions if you have some.

[@nataliee7872]

@@velzer9340 Thanks for the explanation. Can you please also explain what is the point of variables with_to_take and without_to_take? I didn't quite understand what they represent.

[@pandasstory]

Amazing lecture, thanks!

[@Steven-lh5dx]

清晰简介，优美的讲解，致敬

[@ebateru]

Awesome lecture once again. I wonder what is it with these students at MIT? They don't laugh at all and there are some good jokes being thrown at them.

[@beoptimistic5853]

kzbin.info/www/bejne/joGmmHqKbqefqLM 💐.

[@marco.nascimento]

Amazing lecture

[@nickskiadas7338]

Is there any possible way to find an indicative solution to problem set 1?

[@kev9220]

Min 9.17 shouldn't the number of nodes be when there are n items: 2^(n+1) - 1 ?

[@DenCato]

The -1 is correct but it is irrelevant in Big-O notation. Big-O looks at the expense of the algorithm when n gets larger and larger. If n jumps from 100 to 1000, that -1 is really insignificant.

[@chickenicecream1942]

Conclusion: Don't look up answers on Wikipedia xD

[@alute5532]

18:00 "Every Node is a legal solution to the problem" But is it better than the Best? If yes it becomes new best why ? In search tree don't actually build a tree By this trick ( backtrack) to beep track of results Is it hopeless, no ans Rand Corp Dynamic programmingr Oxnard bellman Why it didn't mean anything Issue computation seem grow faster than results Fob 3 calculated in many places We can store it! Dictionary Memoization find optimal solution If that's possibl3, we have optimal substructure (when globally optimal solution can be found How combines optimal solutions with, to local sub problems Crucial note dynamic programming won't help us for sorting Braids optimal soution Q what about other overlapping sub-problems Is there a repetition? (solving same solution?) If no overlap exist (clean solution by dynamic programming is possible I.e. run on knapsack Note zero speed up (why?) If each node the problems are different (in knapsack, things to consider) knapsack is a set (duplicate solution is highly possible Check have same problem to solve more than once Why: Solve same problem despite making different decisions (paths) How Modify max val, to use a memo: To use a 1 add third argument 1. Add a third argument :initially Empty dict Key memo: a tuple (items left, available weight) As items Left are in a list (heap or stack?) Represent it by how long it is (length) (by how long your list is) Computational complexity hcan be very subtle notion Run time fastMaxVal governed by Distinct pairs(available, to consider) Number value consider - small (bound by item's value ) Value (weight available) is hard Bounded by number of distinct (weight sums) It's about combinations, ways I can add up the units (750 call it's either that or lower) Practical problems can be optimization ones Optimal solution is exponentially hard (quadratic equation type) Subproblem Solution always correct Right circumstances: Fast Dynamic always give a good result

[@bjaniak102]

Does anyone know where i can find solution to The 'Roll-over' optimization problem which was included at the end of the lecture's slides?

[@FelipeArayaable]

The code he wrote in the first place it is a bit inefficient anyways, for example the fib function could have been solved with a simple for loop and it would have been as fast as his Fastfib function, but less complicated, ignoring this, I love John Guttag, he explains beautifully and very clear.

[@lcsjr70]

But the point was to explain dynamic programming

[@anonviewerciv]

Buzzwords = government funding. (25:00) 31:31 Memoization.

[@khumoyunakhmedov4562]

good lecture

[@mawkuri5496]

please upload new 6.100b 😅

[@masterchief1520]

I also wanted audience reactions . XD

[@carlosfonseca143]

how is the value for each item determine?

[@stephenadams2397]

A beer in the knapsack is worth 2 in the bush.

[@nassimhaddam7136]

where to find the assigned readings he talked about at the end of the lecture?

[@Syncromatic]

You can check the MIT OCW page for the course (in the description). The book is "Introduction to computation and programming using python:"

[@nassimhaddam7136]

Thanks. I'll check it.

[@jinruifoo7087]

can anyone explain the withval and withtotake portion?

[@beoptimistic5853]

kzbin.info/www/bejne/joGmmHqKbqefqLM 💐.

[@javierurena3367]

Didn't know Flanders was so cultivated in the field of Computation and Data Science

[@katiec5524]

That "Kernal died" made me laugh

[@MrSinalta]

Hi ! Regarding the fast fib function , I don’t get how the dict memo is updated bottom to top as it is assigned new value only inside function . Is because of the fact dict is mutable ?

[@Elite7555]

It is. All objects are passed by reference.

[@RyanScarbrough]

I fear no functions, but that maxVal recursive function, it scares me.

[@RyanScarbrough]

3 days later and I finally understand the gist of it. xD

[@McAwesomeReaper]

Why are there 9 names in the set, but only 8 values and calories? Don't like Cake?

[@kemalware4912]

THIS IS FUCKIN GREAT. Thanks sir.

[@nathanielsabanski3882]

lol exceptions for flow control.... performance hit

[@aulonsal423]

Not a performance hit in python, I think.

[@gmorf33]

Try/except is the norm in python.

[@isbestlizard]

MEMOISATION! i know this because erik told me in 6.006!

[@isbestlizard]

yessssssss i was right!

[@isbestlizard]

hmm what if instead of storing an exact result for a memoisation you just added it as training data for a ML model and then once you had enough stuff 'memoised' started inferencing it to speed hmmm

[@ДжонКонэр]

Great lecture! I hope that all Ukrainians, regardless of age, will be able to study at US universities. 🙌🥰

[@anonviewerciv]

1:11 There's a movie the students probably haven't heard of.

[@beoptimistic5853]

kzbin.info/www/bejne/joGmmHqKbqefqLM 💐.

[@abdulhamidyusuf2848]

33:00 he waited a clap guys and you made him disappointed😅

[@lowhertzhighspl]

Getting to the root of the matter.. - plays at 06:50 mark - The professor says something similar to, "I don't know why these are drawn upside down." With all due respect, maybe it's not the "tree" that's upside down, your interpretation is. Again, getting to the to the ROOT of the matter. Perception is not only interesting, it's everything. Just ask Einstein.

[@mathematicalcoffee2750]

Brandon Lee Except trees actually do have a top and bottom if you go outside

[@jeremyward9363]

camel case python .....

[@zlatanonkovic2424]

DontKnowWhatYoureTalkingAbout

[@EOh-ew2qf]

hehe his jokes are too cute and funny

[@ArunKumar-yb2jn]

Code explanations must be greedy.

[@SphereofTime]

44:34

[@quocvu9847]

34:33

[@davidjames1684]

How can he not know what 2 ^ 64 is? I am glad I don't have him as a teacher.

[@davidjames1684]

To do the same thing over and over is wasteful. Oh really? How about taking a dump, breathing, brushing your teeth, sleeping, having sex, eating....? Stupid statement. He treats his students like seals/sea lions... when they do/say something right, he throws them a "fish"/prize.

[@ALiJ4LIFE]

40:45