Simple. And makes sense. I have been trying to understand dynamic programming for a while, literally. Thank you Ling, and MIT for making it open. Furthermore, I would love to watch the advance level on the topic by him.
To achieve O(n.lg(n)) in the block problem, perhaps given the set of blocks {r1,...rn} we begin by creating two balanced BSTs, one that uses the width as the tree property (what determines if a value becomes a left or right child), and one that uses the height as the tree property. It takes O(2n.log(n)) to build these tree's initially. Now as we add blocks to our stack. Say we just added the block ri with Width Wi, and height Hi, we can first look at our heightBST and find the first block with Hj less than Hi, and clip the entire sub tree, because these values are no longer valid, removing them from the tree, and for each block we remove from the tree, we can also remove them from the WidthBST by searching for them in lg(n) time and removing them, this will take k.log(n) time where k is the number of elements we had to remove. Now we do the same for the WidthBST finding the first block that's Wj < Wi, and we clip this sub tree and removing elements in the height tree similar to as before... Overall we get O(2n.log(n) for the initial tree set up, and then every time we choose a block O(k.log(n)) where k is the number of lookups required for both deletions from the tree's Either way k is bounded by n, giving us O(n.lg(n).
For the stacking box problem, if there were only two dimensions then an O(nlogn) solution is possible. Sorting the boxes by one dimension reduces the problem to LIS (longest increasing subsequence) in the other diimension, which can be solved in nlogn.
@@donotreportmebroI couldn't get how log(n) comes in the play. However, the problem description is in terms of M (distinct coins). N is just a arbitrary argument for the problem. Hence O(M) complexity would have solve the NP-completeness problem. At least this is my understanding
good god I feel bad for whoever took this course from this kid. He gives a portion of the problem statement and waits around for 30 minutes waiting for answers to his simple problem.
Both approaches are symmetric so it doesn't make a difference which end point you choose. (In this example the only allowed directions were (up,right) so it doesn't make sense to start from the endpoint as you will have nowhere to go.)
and if both left as well as right turns are permitted, how are there just two ways to reach the diagonally first node after the starting point? there can be many more possible ways. like go up by 2 steps, take a right and go 1 step, take right and go 1 step more.
the size of N (the number of bits) is given by logN and computational complexity is formally measured in terms of input size. therefore knapsack's complexity in terms of input size is: O(2^(logN)*m) stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time
I doubt if O(m*n) is the solution for the grid problem.. Suppose we are going to m,n = (2, 2) , from x, y = (0, 0). Up (U) or Right (R) are options: P1: UURR P2: URUR P3: URRU P4: RURU P5: RRUU # of distinct path: 5 != 2*2 = m*n ..?
First of all time complexity is not the same as # of distinct paths from 0,0 to 2, 2. Second of all, you have a 3x3 matrix which has 6 distinct paths, you are missing the P6: RUUR.
What the others said, plus Ling clearly said that the answer was m+n. In your example case, 3+3 = 6, which is correct (when you include the missing case RUUR)
O(N*m) - m => Count of different denominations {S1, S2... Sm} Here In the Recursive equation he outlined, you can see its a loop running for Si, (i runs from 1 to m) means, he is computing solutions for all possible denominations and get the min out of it. So, its N*m work. Hope that helps!
@ 16: 00 I couldn't understand the line "One is East West, One is North South" ... ?? I understood about that l ,w are to be compared against l1 and w1 and not w1 and l1 respectively. but how does that english sentence mean this mathematical expression.
Simple. And makes sense. I have been trying to understand dynamic programming for a while, literally. Thank you Ling, and MIT for making it open. Furthermore, I would love to watch the advance level on the topic by him.
Lol prof has that "I'd rather be coding" look on his face
lmao
Working on his own research, yes I am sure he would! Especially when the students are so slow to give answers...
@@benisrood lol it wasn't a criticism, just having some fun with it to boost the video with engagement.
To achieve O(n.lg(n)) in the block problem, perhaps given the set of blocks {r1,...rn} we begin by creating two balanced BSTs, one that uses the width as the tree property (what determines if a value becomes a left or right child), and one that uses the height as the tree property. It takes O(2n.log(n)) to build these tree's initially. Now as we add blocks to our stack. Say we just added the block ri with Width Wi, and height Hi, we can first look at our heightBST and find the first block with Hj less than Hi, and clip the entire sub tree, because these values are no longer valid, removing them from the tree, and for each block we remove from the tree, we can also remove them from the WidthBST by searching for them in lg(n) time and removing them, this will take k.log(n) time where k is the number of elements we had to remove. Now we do the same for the WidthBST finding the first block that's Wj < Wi, and we clip this sub tree and removing elements in the height tree similar to as before... Overall we get O(2n.log(n) for the initial tree set up, and then every time we choose a block O(k.log(n)) where k is the number of lookups required for both deletions from the tree's
Either way k is bounded by n, giving us O(n.lg(n).
clear, precise, good hand writing ... wish to see a bit more smiling faces from Ling
Me too
For the stacking box problem, if there were only two dimensions then an O(nlogn) solution is possible.
Sorting the boxes by one dimension reduces the problem to LIS (longest increasing subsequence) in the other diimension, which can be solved in nlogn.
Universal Hashing and Perfect Hashing starting @ 34:27
for the compatible set problems, in order to achieve nlogn, I think we can use kd-tree
How does log(n) represent the size of n input? that part was too quick. @14:00
I wonder if you eventually figured this out? Just watching this now
@@donotreportmebroI couldn't get how log(n) comes in the play. However, the problem description is in terms of M (distinct coins). N is just a arbitrary argument for the problem. Hence O(M) complexity would have solve the NP-completeness problem. At least this is my understanding
it's the concept of pseudo polynomial, use of binary representation
Ling Ren is awesome. Thanks for grilling them¡
good god I feel bad for whoever took this course from this kid. He gives a portion of the problem statement and waits around for 30 minutes waiting for answers to his simple problem.
This is a recitation not a lecture...fool
shouldn't we start from the end point? for the robot example
Both approaches are symmetric so it doesn't make a difference which end point you choose.
(In this example the only allowed directions were (up,right) so it doesn't make sense to start from the endpoint as you will have nowhere to go.)
@8:30 I am not sure why the subproblems are defined as min(Mc(N-si)+1)?
clear and concise, nicely done
30/52 minutes waiting for answers
Wen Chu how's yours ?
is this question clear?
This is a recitation rather than then actual course.
and if both left as well as right turns are permitted, how are there just two ways to reach the diagonally first node after the starting point? there can be many more possible ways. like go up by 2 steps, take a right and go 1 step, take right and go 1 step more.
doesn't even explain the problem! are we supposed to read his mind?
13:46 could anyone explain why is it logN? I'm really confused here...
the size of N (the number of bits) is given by logN and computational complexity is formally measured in terms of input size. therefore knapsack's complexity in terms of input size is: O(2^(logN)*m) stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time
@@IkerLissarrague Ah it makes sense, thank you! :D
@@xihu4067 seems like the comment is gone. What was the answer?
The lack of throwing freesbees clearly shows in the activity of the audience.
Difficulty level: ASIAN.
I doubt if O(m*n) is the solution for the grid problem..
Suppose we are going to m,n = (2, 2) , from x, y = (0, 0).
Up (U) or Right (R) are options:
P1: UURR
P2: URUR
P3: URRU
P4: RURU
P5: RRUU
# of distinct path: 5 != 2*2 = m*n
..?
RUUR is gone here.
First of all time complexity is not the same as # of distinct paths from 0,0 to 2, 2. Second of all, you have a 3x3 matrix which has 6 distinct paths, you are missing the P6: RUUR.
O(m*n) is the Big O notation // time complexity not the solution...just shows how much you understand what's actually going on lol
What the others said, plus Ling clearly said that the answer was m+n.
In your example case, 3+3 = 6, which is correct (when you include the missing case RUUR)
what's the difference between these R videos and the normal lecture?
R = recitation, and is taught by the professors' assistants
@@ranggagarmastewira3344 This guy is so good, I didn't even think he was the assistant.
@@user-qc9rq3vb2z you have to be that good to be even an assistant at MIT
Guys, so sorry, but i didn't understand how runtime is (N*m) for the minimum number of coins problem. Can someone please explain?
O(N*m) - m => Count of different denominations {S1, S2... Sm}
Here In the Recursive equation he outlined, you can see its a loop running for Si, (i runs from 1 to m) means, he is computing solutions for all possible denominations and get the min out of it. So, its N*m work. Hope that helps!
Vigneshwar P Thankyou so much!
Very neat.
I guess Mr. Ling doesn't like What he is Doing !!
this guy is hella smart
I agree, but simultaneously is probably the worst teacher
Hello sir for DP there is no exact formula to find the answer,
46:11 second line that should be an inequality
that digression is a bit hard to understand
Ling Ren for Presidency.
miss Victor Costan
Same here :-(
Wonderful speech bro :D
@ 16: 00 I couldn't understand the line "One is East West, One is North South" ... ?? I understood about that l ,w are to be compared against l1 and w1 and not w1 and l1 respectively. but how does that english sentence mean this mathematical expression.
Nice
clear, nice handwriting, thanks
if the robot can go either up or right only, wont there be just one possible path?? rest all would require a left turn .....
this guy looks like a character from a cartoon
very good explanation
It pains me how dead this class is. But I like the lecturer.
video says DP but at 35:00 he goes into hashing lol
"the third option, of course, we can just call it a day" haaha!
considering that was at the 33 minute mark, clearly didn't happen
?
maybe a little more emotion?
it's a computer science lecture...
Not a movie...😂
@@TheMasterfulcreator It's not even a lecture, it's a recitation
@@cvxcfv not wrong.