2. Divide & Conquer: Convex Hull, Median Finding

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-0...
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
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@anythingstudio5208]

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

[@coolclay27]

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.

[@mrloldude135]

Median finding @53:29

[@wendyyhampton]

52:16 *

[@thedailynoodle8363]

You guys really stepped up the camera work

[@DrPastah]

lol

[@alute5532]

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

[@bleakmess]

convex hull is better from 07:00

[@jayquelin]

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

[@akshat1234100]

i love the 720p after watching 6.006 in 360p

[@superdupe8]

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.

[@SkSami007]

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

[@jimmypi7]

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 "

[@niazahmad7823]

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.

[@ceciliaw1065]

Crystal clear explanation, what an amazing lecturer, just wow

[@kaushikmangaprasad4575]

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

[@kirillkozlov5395]

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

[@niazahmad7823]

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

[@dohyun0047]

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

[@gnpar]

You don't need to sort them or arrange them like that, you just need to find the median of that row. The pictures are simply to show that once you find it, you have a situation where roughly half of the elements are < x and roughly half are > x. Once you have x you go back to the original problem and, since your pivot is now roughly in the middle, you have O(n) complexity on the D&C algorithm.

[@vermoidvermoid7124]

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

[@lekhoa6552]

awesome explanations!!!

[@donotreportmebro]

53:40 Big Theta is rarely satisfactory. We want big O to be optimal, specifically O(n) in the case of finding a median.

[@dwarakeshkotipatruni6578]

Bro I didn't understand the whole lecture can you please help me

[@Tibetan-experience]

thank you

[@badr-eddineelbatouri4544]

there is a small problem, when having n point we can only draw n*(n-1)*2 segments not n*n. having 3 point ABC will result in AB AC BC BA CA BC and if we are using dynamic programming we can remove the BA CA CB thus AB AC BC only.

[@venkateshnaresh966]

yes, that's true. But look at the order of growth. The dominant term here is n^2. The linear term is ignored since it doesn't grow as fast as the quadratic term

[@WeirdAlSuperFan]

Yeah that's O(n^2). Also you meant n(n-1)/2 (n choose 2). Don't sweat the small stuff in complexity calculations

[@stormanning1163]

Excellent explanations!

[@o.y.930]

can somebody explain why is it T(n/5) and not 5T(n/5) in 1:17:29. Aren't we doing the recursion 5 times each step.

[@mytennisjourney4949]

N elements divided into N/5 columns, each column is sorted by constant time, every column has a median, so there are N/5 medians. And we use algorithm recursively, we find the median of these medians, which means T(n / 5)

[@mytennisjourney4949]

The key point here is that the problem we need to solve is find median, we assume we solve the problem, and we use this solution to find “median of medians” (pick X in lesion), to help us solve the problem “find a median”.

[@naomim1207]

Why used a Doubly Linked List for Convex Hull?

[@Drethron]

May not divide and concur as easily but couldn't you average all of the points to find the center, then determine if a point is a smaller raduis away relative to the points on either side? Either way, very nice videos so far.

[@tear728]

I'm pretty sure that would be O (n^2) still. I might be wrong on that though

[@loona8398]

I really don't know why I have such a thick brain when it comes to algorithms?

[@videofountain]

At this time point kzbin.info/www/bejne/e6vIinxtpZ6AoLch1m27s ... the chalk writing was likely intended to be recursively ... [return Select(C, i-k)] ... rather than ##[return (C, i -k)]##. [Select] function name for recursion.

[@jeongminyoun5388]

Where did 7n+7/10 + 7 come from in the end?

[@thinhnguyenvan7003]

Can someone explain for me that. Why Arrange S into columns of size 5 and sort each column take linear time? suppose that sorting take oder nlogn. So time complex here is k* 5log5 time which is k equal n/5.

[@gnpar]

You just explained it yourself. You ended up with complexity (n/5)5log5. That's n multiplied by some constant log5, it's still O(n). Note that it would be exactly the same if sorting took n^4 or 4^n, it doesn't matter, you're always sorting five elements.

[@DommageCollateral]

thanks. better than my frkn uni

[@Upendra237]

🎉

[@dineshjagai]

Great lecture :D

[@SandyRocks007]

Merging convex hull 23:59

[@Renembrence]

You fucking saint I love you

[@mritunjay_99]

Where is Morty?

[@marlow893]

recording could be better if at least a few seconds is left to see the board without the teacher. easier to take notes.

[@atulavhad1661]

You could pause the video while taking notes or download the subscripts. Also, lecture notes are available on ocw.mit.edu

[@bhavneetsingh6893]

why it is n3 at 20:45

[@diegoarcelli8902]

I think because there are O(n^2) possible segments and for each of them you have to verify if the n points (except for the two crossed by the segment) are all in one of the two half plain defined by the segment. So you do an O(n) operation O(n^2) times therefore the cost is O(n^3).

[@nikolapetrovic4415]

Whether this video is accelerated or this guy just has too fast movements?

[@holdenmcgroin8917]

The BS stops at 7:10

[@tirthjayswal9895]

bestttttttttttttttttttttttttttt

[@jamesbrean8004]

LoL

[@prajapatarun5711]

Again Indian fella

[@rahulkashyap840]

kya bkwas pda rh a h yaar

[@Outloud444]

Funny .. YOU ALL would wind up DEAD -- using this formula -- you are better off -- using John Nash's Equilibrium Theory

[@weitengli179]

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. en.wikipedia.org/wiki/Gift_wrapping_algorithm

[@erikjohnson1925]

Good point! And if one allows for an output sensitive algorithm, then the asymptotically optimal algorithm is either Chin's Algorithm or Kirkpatrick-Seidel with O(n log h) time

[@keelwakamar]

Can't i propose a situation where all points are on the convex hull? If that case were true, then it's complexity would basically be O(n²) right?

[@erikjohnson1925]

@@keelwakamar I don't think this is correct. I think that if you keep track of points on the hull, you only need to check the "open" end (assuming that point is actually on the hull e.g. lowest x-value point which can be found in O(n)). This means the number of points to check decreases by 1 on every iteration

[@keelwakamar]

@@erikjohnson1925 you still get O(n²) when you do asymptomatic analysis on that. You can try it yourself, or check how selection sort is O(n²) eventhough it does exactly what you mentioned.

[@erikjohnson1925]

@@keelwakamar My mistake, you are completely correct. For some reason, I really expected that case to degenerate to O(n log n). I guess you need Chin's Algorithm or Kirkpatrick-Seidel to get the O(n log n) when all points lie on the hull

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

[@tuhinmukherjee8141]

Yes, true but the complexity lies in the determination of the four points to be linked.

[@hungrypigeon7246]

How do we prove that the figure formed in the first case by joining the segments convex?

[@ericwilson8665]

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

[@rishabharijeet4151]

40:33

[@jayhoeliotdecabrio4050]

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.

[@Outloud444]

Merging 2 groups … as they both want ALL the MONEY -- good luck --- Pay to Play -- Money is #1

[@KeshariPiyush24]

Median of Median part is not good....other than that amazing lecture

[@shubhamtalks9718]

median finding kzbin.info/www/bejne/e6vIinxtpZ6AoLc 52:18

[@charlottetreesageorge2230]

Thank you so much for making this available for all

[@brendawilliams8062]

Thx.

[@olier1]

2015 and one of the best Technical University still use blackboard

[@jamesking2439]

The blackboard sets the mood.

[@WayneRadinsky]

It works.

[@kevidimitrisceci8096]

I don't know why someone has to go to university when exists this.

[@olaafelumo4754]

Dimitris Ceci I know right ? But you get tested in school. You don’t get tested here

[@rbrtchng]

how do you get the medium of mediums?

[@anmol-gupta]

If we have n/5 columns then to find the median of medians we'll have to call the Select function on the list of medians. We're basically computing 1 subproblem that is 1/5th the size of the original. Hence, the T(n/5) term for finding the median of medians.

[@aobcd.8663]

I feel other videos for DS are more useful than these famous universities. These guys presume you know everything

[@bisnusarkar9678]

it is an awesome lecture...

[@faisalsal1]

The course is too much abstract and theoretical with a high dose of verbosity. Just cut the chase and demonstrate using a sample of numbers how the algorithm finds the medium? Too much beating around the bush without hitting the point. I believe these kind of courses are only to pass the exams but definitely useless if preparing for technical interviews or to solve any programming challenge.

[@debarkasengupta5351]

Slides would save a lot of his time, perhaps more content can be delivered.

[@mitocw]

Lecture notes are available on MIT OpenCourseWare at: ocw.mit.edu/6-046JS15. Best wishes on your studies!

[@ankushm3t]

meh, slides are bad for teaching IMO. I found all black board type lectures much easier to follow even at 1.5x speed