2. Divide & Conquer: Convex Hull, Median Finding
Вставка
- Опубліковано 4 лют 2025
- 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
Course starts at 7:10
Merging convex hull 23:59
Median finding 53:29
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.
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
convex hull is better from 07:00
Median finding @53:29
52:16 *
You guys really stepped up the camera work
lol
Such a brilliant lecture --i particular love the visual examples!! Thank you MIT OWC
i love the 720p after watching 6.006 in 360p
A bunch of thanks for your video lessons. It really helps me understand the Algorithm a way deeper..
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 "
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.
Crystal clear explanation, what an amazing lecturer, just wow
The median finding algorithm is so clever
really good lecture, well explained.. especially the visual cues
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
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
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?
@@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
@@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.
@@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
b2 and b4 switch places at 36:15, so the points in "b" sub-convex hull become ordered counter-clockwise
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.
43:57 T(n)= +theta(n)=Theta(Logn)
MMerging Convex hull
.
So is he finding the median of medians using the same approach again?
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.
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)
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”.
In median of median do we sort the "medians" row too?
if not how can we guarantee those picture? @1:12:11
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.
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.
53:40 Big Theta is rarely satisfactory. We want big O to be optimal, specifically O(n) in the case of finding a median.
Bro I didn't understand the whole lecture can you please help me
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?
Yes, true but the complexity lies in the determination of the four points to be linked.
Fantastic example. That's so appreciated. Made it so clear.
Thank you so much for making this available for all
"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?
How do we prove that the figure formed in the first case by joining the segments convex?
I wish i could be intelligent enough to understand this enough to make it into code....but I am below average IQ for this.
2015 and one of the best Technical University still use blackboard
The blackboard sets the mood.
It works.
awesome explanations!!!
I really don't know why I have such a thick brain when it comes to algorithms?
Excellent explanations!
Where did 7n+7/10 + 7 come from in the end?
Why used a Doubly Linked List for Convex Hull?
thank you
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.
I'm pretty sure that would be O (n^2) still. I might be wrong on that though
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.
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.
Merging convex hull 23:59
You fucking saint I love you
thanks. better than my frkn uni
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.
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
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
why it is n3 at 20:45
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).
Great lecture :D
Thx.
how do you get the medium of mediums?
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.
At this time point ua-cam.com/video/EzeYI7p9MjU/v-deo.htmlh1m27s ... 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.
I don't know why someone has to go to university when exists this.
Dimitris Ceci I know right ? But you get tested in school. You don’t get tested here
The BS stops at 7:10
Where is Morty?
it is an awesome lecture...
median finding ua-cam.com/video/EzeYI7p9MjU/v-deo.html 52:18
Median of Median part is not good....other than that amazing lecture
🎉
40:33
Merging 2 groups … as they both want ALL the MONEY -- good luck --- Pay to Play -- Money is #1
recording could be better if at least a few seconds is left to see the board without the teacher. easier to take notes.
You could pause the video while taking notes or download the subscripts. Also, lecture notes are available on ocw.mit.edu
Whether this video is accelerated or this guy just has too fast movements?
I feel other videos for DS are more useful than these famous universities.
These guys presume you know everything
bestttttttttttttttttttttttttttt
LoL
Again Indian fella
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.
kya bkwas pda rh a h yaar
Slides would save a lot of his time, perhaps more content can be delivered.
Lecture notes are available on MIT OpenCourseWare at: ocw.mit.edu/6-046JS15. Best wishes on your studies!
meh, slides are bad for teaching IMO. I found all black board type lectures much easier to follow even at 1.5x speed
Funny .. YOU ALL would wind up DEAD -- using this formula -- you are better off -- using John Nash's Equilibrium Theory