2. Divide & Conquer: Convex Hull, Median Finding
Vložit
- čas přidán 3. 03. 2016
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-046JS15
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
Median finding @53:29
52:16 *
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.
You guys really stepped up the camera work
lol
A bunch of thanks for your video lessons. It really helps me understand the Algorithm a way deeper..
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
Such a brilliant lecture --i particular love the visual examples!! Thank you MIT OWC
really good lecture, well explained.. especially the visual cues
Crystal clear explanation, what an amazing lecturer, just wow
b2 and b4 switch places at 36:15, so the points in "b" sub-convex hull become ordered counter-clockwise
Fantastic example. That's so appreciated. Made it so clear.
i love the 720p after watching 6.006 in 360p
Thank you so much for making this available for all
Excellent explanations!
awesome explanations!!!
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 "
How do we prove that the figure formed in the first case by joining the segments convex?
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.
So is he finding the median of medians using the same approach again?
thank you
Where did 7n+7/10 + 7 come from in the end?
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.
Why used a Doubly Linked List for Convex Hull?
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
Great lecture :D
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.
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.
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.
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”.
it is an awesome lecture...
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).
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
At this time point czcams.com/video/EzeYI7p9MjU/video.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.
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.
Thx.
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
2015 and one of the best Technical University still use blackboard
The blackboard sets the mood.
It works.
Where is Morty?
Median of Median part is not good....other than that amazing lecture
Merging convex hull 23:59
You fucking saint I love you
thanks. better than my frkn uni
median finding czcams.com/video/EzeYI7p9MjU/video.html 52:18
Whether this video is accelerated or this guy just has too fast movements?
🎉
40:33
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
Merging 2 groups … as they both want ALL the MONEY -- good luck --- Pay to Play -- Money is #1
bestttttttttttttttttttttttttttt
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
The BS stops at 7:10
I feel other videos for DS are more useful than these famous universities.
These guys presume you know everything
LoL
Again Indian fella
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
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.
Funny .. YOU ALL would wind up DEAD -- using this formula -- you are better off -- using John Nash's Equilibrium Theory