R5. Dynamic Programming

[@AnitShrestha]

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.

[@stormanning1163]

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

[@jamesqiu6715]

clear, precise, good hand writing ... wish to see a bit more smiling faces from Ling

[@akshaymathur2225]

Me too

[@paxdriver]

Lol prof has that "I'd rather be coding" look on his face

[@joeybing3774]

lmao

[@benisrood]

Working on his own research, yes I am sure he would! Especially when the students are so slow to give answers...

[@paxdriver]

@@benisrood lol it wasn't a criticism, just having some fun with it to boost the video with engagement.

[@Squirrelschaser]

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.

[@mattf9076]

@8:30 I am not sure why the subproblems are defined as min(Mc(N-si)+1)?

[@TooCoolForBZ]

How does log(n) represent the size of n input? that part was too quick. @14:00

[@donotreportmebro]

I wonder if you eventually figured this out? Just watching this now

[@akurmustafa_]

@@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

[@scotfsh5014]

it's the concept of pseudo polynomial, use of binary representation

[@mrleolink]

for the compatible set problems, in order to achieve nlogn, I think we can use kd-tree

[@mech_builder7998]

Universal Hashing and Perfect Hashing starting @ 34:27

[@xihu4067]

13:46 could anyone explain why is it logN? I'm really confused here...

[@IkerLissarrague]

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

[@xihu4067]

@@IkerLissarrague Ah it makes sense, thank you! :D

[@vahanpoghosyan1581]

@@xihu4067 seems like the comment is gone. What was the answer?

[@дантээлрик]

Ling Ren is awesome. Thanks for grilling them¡

[@breezysaint9539]

clear and concise, nicely done

[@KaramAbuGhalieh]

shouldn't we start from the end point? for the robot example

[@sumofentropy]

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

[@grim4a275]

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.

[@alimustafa2682]

30/52 minutes waiting for answers

[@taureandials1246]

Wen Chu how's yours ?

[@HippoShemp]

is this question clear?

[@Bridgelessalex]

This is a recitation rather than then actual course.

[@NytronX]

Difficulty level: ASIAN.

[@zsoltbr]

The lack of throwing freesbees clearly shows in the activity of the audience.

[@shaoin3295]

doesn't even explain the problem! are we supposed to read his mind?

[@chrislam1341]

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

[@popferi9573]

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.

[@cvxcfv]

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

[@benisrood]

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)

[@uniswang]

what's the difference between these R videos and the normal lecture?

[@ranggagarmastewira3344]

R = recitation, and is taught by the professors' assistants

[@user-qc9rq3vb2z]

@@ranggagarmastewira3344 This guy is so good, I didn't even think he was the assistant.

[@yushpi]

@@user-qc9rq3vb2z you have to be that good to be even an assistant at MIT

[@useless0ful]

Guys, so sorry, but i didn't understand how runtime is (N*m) for the minimum number of coins problem. Can someone please explain?

[@vigneshwarp3462]

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!

[@useless0ful]

Vigneshwar P Thankyou so much!

[@x0cx102]

46:11 second line that should be an inequality

[@Anubis10110]

I guess Mr. Ling doesn't like What he is Doing !!

[@bronsonschnitzel7493]

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.

[@cvxcfv]

This is a recitation not a lecture...fool

[@techfornoobs4241]

this guy is hella smart

[@franciszekwieczorek5292]

I agree, but simultaneously is probably the worst teacher

[@bablobko]

Ling Ren for Presidency.

[@akshaymathur2225]

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

[@SahilThakur26]

that digression is a bit hard to understand

[@sextolife]

Hello sir for DP there is no exact formula to find the answer,

[@qijinliu4024]

Wonderful speech bro :D

[@akshaymathur2225]

Very neat.

[@vishnukl]

miss Victor Costan

[@AMANKUMAR-oh1zt]

Same here :-(

[@grim4a275]

if the robot can go either up or right only, wont there be just one possible path?? rest all would require a left turn .....

[@chaoschao9432]

clear, nice handwriting, thanks

[@codyheiner3636]

It pains me how dead this class is. But I like the lecturer.

[@krokenstiv8777]

this guy looks like a character from a cartoon

[@lxkp3233]

very good explanation

[@linuxmaster2327]

Nice

[@x0cx102]

"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

[@ytg6663]

?

[@deathbombs]

video says DP but at 35:00 he goes into hashing lol

[@dandong8329]

maybe a little more emotion?

[@TheMasterfulcreator]

it's a computer science lecture...

[@arunm619]

Not a movie...😂

[@cvxcfv]

@@TheMasterfulcreator It's not even a lecture, it's a recitation

[@TheMasterfulcreator]

@@cvxcfv not wrong.