2. Optimization Problems
Вставка
- Опубліковано 30 вер 2024
- 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
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
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
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.
@@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.
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).
This was identified by many commentators in Lecture 1 as well. It's a mistake.
I believe Eric Grimson, Ana Bell and JohnGuttag are one of the best lecturers at MIT.
Ramin Dehghan some of*
Gilbert Strang
Same feeling bro
But that may be because you only took 60001 and this course
😁
How about prof. Eric Demaine?
*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
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.
bro is not enjoying the show
One of the courses that I can say changed my life.
ua-cam.com/video/XPCgGT9BlrQ/v-deo.html 💐.
I love how he always looks like he's possibly trying to suppress a laugh. What an awesome guy!!
Is there any possible way to find an indicative solution to problem set 1?
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?
Code explanations must be greedy.
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
Buzzwords = government funding. (25:00)
31:31 Memoization.
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.
where to find the assigned readings he talked about at the end of the lecture?
You can check the MIT OCW page for the course (in the description). The book is "Introduction to computation and programming using python:"
Thanks. I'll check it.
Min 9.17 shouldn't the number of nodes be when there are n items: 2^(n+1) - 1 ?
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.
Conclusion: Don't look up answers on Wikipedia xD
Awesome! I've got really suprised with fast fibonacci's speed. Great job!
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.
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.
Why are there 9 names in the set, but only 8 values and calories? Don't like Cake?
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]
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
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.
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.
@@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.
My favorite instructor for this course!
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.
But the course was taught in Fall 2016 :p. Which course were you talking about ?..
@@sarthakbindal7660 probably same course different year.
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..
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).
Lies again? Oil Petrol
Thank you! I'm glad I can take this course
A beer in the knapsack is worth 2 in the bush.
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
can anyone explain the withval and withtotake portion?
ua-cam.com/video/XPCgGT9BlrQ/v-deo.html 💐.
please upload new 6.100b 😅
@21:00 For reproducible random numbers seed(int) function is used in R
I also wanted audience reactions . XD
THIS IS FUCKIN GREAT. Thanks sir.
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.
ua-cam.com/video/XPCgGT9BlrQ/v-deo.html 💐.
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 ?
It is. All objects are passed by reference.
I fear no functions, but that maxVal recursive function, it scares me.
3 days later and I finally understand the gist of it. xD
how is the value for each item determine?
lol exceptions for flow control.... performance hit
Not a performance hit in python, I think.
Try/except is the norm in python.
Amazing lecture, thanks!
hehe his jokes are too cute and funny
MEMOISATION! i know this because erik told me in 6.006!
yessssssss i was right!
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
Thanks MIT OCW and Dr John Guttag !!!
That "Kernal died" made me laugh
Im glad i found this
44:34
34:33
good lecture
thanks,mit
camel case python .....
DontKnowWhatYoureTalkingAbout
Didn't know Flanders was so cultivated in the field of Computation and Data Science
Amazing lecture
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.
But the point was to explain dynamic programming
40:45
Great lecture! I hope that all Ukrainians, regardless of age, will be able to study at US universities. 🙌🥰
33:00 he waited a clap guys and you made him disappointed😅
1:11 There's a movie the students probably haven't heard of.
ua-cam.com/video/XPCgGT9BlrQ/v-deo.html 💐.
清晰简介，优美的讲解，致敬
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.
Brandon Lee Except trees actually do have a top and bottom if you go outside
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.
How can he not know what 2 ^ 64 is? I am glad I don't have him as a teacher.