R5. Dynamic Programming

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Ling Ren

In this recitation, problems related to dynamic programming are discussed.

License: Creative Commons BY-NC-SA

[paxdriver]

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

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

[jamesqiu]

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

[stormanning]

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

[mattf]

@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

[mrleolink]

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

[mech_builder]

Universal Hashing and Perfect Hashing starting @ 34:27

[xihu]

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

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

[KaramAbuGhalieh]

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

[grima]

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.

[uniswang]

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

[shaoin]

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

[uselessful]

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

[chrislam]

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

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

Ling Ren is awesome. Thanks for grilling them¡

[sextolife]

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

[bronsonschnitzel]

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.

[xcx]

46:11 second line that should be an inequality