2. Divide & Conquer: Convex Hull, Median Finding

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
Instructor: Srinivas Devadas

In this lecture, Professor Devadas introduces divide-and-conquer algorithms and problems that can be solved using divide-and-conquer approaches.

License: Creative Commons BY-NC-SA

[anythingstudio]

Course starts at 7:10
Merging convex hull 23:59
Median finding 53:29

[coolclay]

Srinivas Devadas is the best lecturer I have ever encountered. He's amazingly clear, but does not over-explain. It's a pity he's not teaching 6.046 anymore.

[thedailynoodle]

You guys really stepped up the camera work

[alute]

Convex hull hull 11:00
Definition 12:27
Smallest polygon containing all points ch(S)
Sequence boundaries
Doubly LinkedList
21:14 Break me up by drawing half-planes
Left plane is one sub problem
Right line is another problem
Find convex hull for each of subprolems -when you get a hint brute force won't work
47:10 how do o remove the lines
Find upper tangent & lower tangent

[superdupe]

convex hull explanation = good
median finding = not so good. Then again, I feel like he didn't have enough time. There's a lot of steps to the median problem, but he was definitely rushing through it and more or less just telling the answer instead of giving much intuition behind it.

[jayquelin]

Such a brilliant lecture --i particular love the visual examples!! Thank you MIT OWC

[akshat]

i love the 720p after watching 6.006 in 360p

[niazahmad]

I initially found it confusing when, around the 38:00 mark, it seemed like every single element in the left hull was being compared with b1. This led me to wonder if, in the worst case, we might end up comparing every element of the left hull with every element of the right hull, which would be highly inefficient. However, that’s not actually the case.

The reason they compare elements with b1 is because b1 represents the maximum value at that point in the process. The code clarifies that each element is processed only once. For example, if b4 proves to be a better candidate, it replaces b1 and the comparison moves forward. If b1 was revisited, it would indicate that no better candidate was found, meaning b1 only needs to be processed as the best candidate for that moment. Apologies if I didn’t explain it clearly.

[SkSami]

A bunch of thanks for your video lessons. It really helps me understand the Algorithm a way deeper..

[jimmypi]

Did anyone find maybe the definition of rank at :

501 00:53:37, 070 --> 00:53:53, 880 And so in general, we're going to define, given a set of n numbers, define rank of x
502 00:53:53, 880 --> --00:54:06--, 510 as the numbers in the set that are greater than-- I'm sorry, less than or equal to x.
503 00:54:06, 510 --> 00:54:09, 270 I mean, you could have defined it differently. We're going to go with less than or equal
504 00:54:09, 270 --> 00:54:10, 750 to.

is a typo?

I checked the written note and find "number of numbers in the set that are smaller than x" makes more sense compared to rank defined on the black board in the video as "numbers in the set that are smaller than x"

In short :
"number of numbers in the set" versus "numbers in the set "

[vermoidvermoid]

really good lecture, well explained.. especially the visual cues

[weitengli]

44:00 Gift wrapping may be better than devide & conquer; it has O(nh) time complexity (not nlogn as the professor mentioned), where n is the number of points and h is the number of points on the convex hull.

[kaushikmangaprasad]

So is he finding the median of medians using the same approach again?

[ceciliaw]

Crystal clear explanation, what an amazing lecturer, just wow

[ericwilson]

Fantastic example. That's so appreciated. Made it so clear.

[dohyun]

In median of median do we sort the "medians" row too?
if not how can we guarantee those picture? @1:12:11

[jayhoeliotdecabrio]

please note that the diagram numbering is done worng by mistake if you trace the algorithm with the diagram drawn by professor then you will get confused so check out the notes at ocw.

[niazahmad]

"while (y(i, j + 1) > y(i, j) or y(i − 1, j) > y(i, j))
if (y(i, j + 1) > y(i, j)) [ move right finger clockwise
j = j + 1( mod q)" My question is how is this code moving the point in the clock-wise direction it is just incrementing j and there could be a point that has j just next to the one we are currrently on and it could lie in the anti-clock wise fashion. How is this code making sure that it moves it in the clockwise direction?

[kirillkozlov]

b2 and b4 switch places at 36:15, so the points in "b" sub-convex hull become ordered counter-clockwise

[shampoable]

assuming the result of ConvexHull(Set) is a doubly linked list, wouldn't combining two of them be O(1), as only 4 points need to be linked?