Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit mitop courseware at ocw.mit.edu all right good morning everyone let's get started so we're going to start 6046 in Earnest today uh we're going to start with our first module on divide and conquer uh you've all seen divide and conquer algorithms before merge s is a classic divide and conquer algorithm I'm going to spend just a couple of minutes talking about the Paradigm give you a slightly more general setting than merge sort and then we'll get into two really cool divide and conquer uh uh problems in the sense that these are problems for which divid and Conquer works very well namely convex Hull and median finding so before I get started on the material uh let me remind you that uh you should be signing up for a registation section on stellar and please do that even if you don't plan on attending sections because we need that uh so we can assign your problem sets to be graded okay so that's our way of uh partitioning problem sets as well uh and then the other thing is uh problem set one is going to go out today and uh it's a onewe problem set all problem sets are going to be a a week in duration U please read these problem sets the day they they come out spend 5 10 minutes reading them um some things are going to look like they're magic that they're uh you know how could I possibly prove this uh if you think about it for a bit it'll become obvious we promise you that but get started early don't get started uh you know at 700 p.m.
when we have a 11:59 p.m. deadline on Thursday right the that 4 hours or 5 hours of time may not be enough to go from magical to obvious okay so um let's get started with the Paradigm associated with divide and conquer it's just a beautiful notion that you can break up a problem into smaller parts and somehow compose the solutions to the smaller parts and of course the details are going to be what's important when we take a particular problem instance but let's say we given a problem of size n we're going to divide it into a sub problems I'll put that in quotes so you know it's uh a symbol uh a sub problems of size n / B and here a could is is an integer and a is going to be greater than or equal to one it could be two it could be three it could be four this is the generalization I alluded to and B does not have to be too or even an integer but it has to be strictly greater than one otherwise you know there's no notion of uh divide and conquer you're not breaking things up into smaller problems so B should be strictly greater than one right so that's the the general setting and then you solve each sub problem recursively and the idea here is that once the sub problems become really small they become constant size It's relatively easy to solve them you can just do exhaustive search uh if you have 10 elements uh and uh you're doing effectively a cubic search well 10 cubed is a, that's a constant you're in great shape right as long as the constants are small enough and so you're going to recurse until these problems get small and then typically this is not true for all divide and concer approaches but for most of them and certainly the ones we're going to cover uh today the smarts is going to be in the combination step when you combine these problems uh the solutions of these sub problems into the overall solution and so that's uh the story um typically what happens in terms of efficiency is that you can write a recurrence that's associated with this divide and conquer algorithm and you say t of n which is the running time for a problem of size n is going to be a * T ofn / B and this is a recurrence plus the work that you need to do for the merge operation are the combine this is the same as merge um and so you get a recurrence and you're not quite done yet in terms of the analysis because once you have the recurrence you do have to solve the recurrence and it's usually not that hard and certainly it's not going to be particularly difficult for the divide and conquer examples that we're going to look at at least today but we also have this theorem that's called the master theorem that uh is essentially something where you can fairly mechanically plug in the A's and the B's and whatever you have there maybe it's Theta n maybe it's Theta n square and get the solution to the recurrence I'm actually not going to do that today but you'll here once again about the master theorem uh tomorrow in in section and it's a fairly straightforward template that you can use for most of the divid and Concor examples we're going to look at in 046 with one exception uh that we'll look at in median finding today that will simply give you the solution to the recurrence okay so you've seen most of these things before that's a little bit of setup and so let's Dive Right In into convex Hull which is uh my favorite problem when it comes to using divide and concer so convex Hall I got a little prop here uh which will save me from writing on the board and hopefully be more more understandable but the idea here is that um in this case we have a a two-dimensional problem problem with uh a bunch of points in a two-dimensional plane uh you can certainly do convex Hull for three dimensions many dimensions and uh convexity is something that is a fundamental notion in optimization and maybe we'll get to that in 6046 in advanced topics maybe not but in the context of today's lecture what we're interested in doing is essentially finding an envelope or a hull associated with the collection of points on a two-dimensional plane and this Hull obviously is going to be something as you can guess um that encloses all of these points okay so uh what I have here uh if I make this string taught enough this is not working out so well but I think you get the picture uh all right so that's not a convex Hull okay this this is not a convex Hull for the reason that I have a bunch of points outside of the hull all right so let me just that is a convex H okay um and now if I start stretching like that or like this or like that that's still a convex Hall okay so that's the game we have to uh find an algorithm and we'll look at a couple of different ones that will find all of these segments that are associated with this convex Hall okay so this is a segment that's part of the convex Hall that's a segment that's part of the convex Hull if in fact I had something like this this and and this was stretched out because I have those two points outside the convex H this may still be a segment that's part of the correct convex Hull but this one was is not right so so that's the the game here is to find these segments so if you're going to be working with segments or tangents uh they're going to be used synonymously that are all of the tangents or segments associated with the entirety of the convex Hull and we have to discover them and the only input that we have is the set of points X I Yi coordinates okay and there's just a variety of algorithms that you can use to do this the the the one that I I wish I had time to explain but I'll just mention is what's called a gift wrapping algorithm where I you might not have done this but I guarantee you uh that you probably have taken a misshapen gift right and try to wrap it in gift wrapping paper and when you're doing that you're essentially if you're doing it right you're essentially trying to find the convex Hull of this three-dimensional structure you're trying to tighten it up you're trying to find the minimum amount of graph of gift wrapping paper I'm not sure you ever thought about minimizing gift wrap paper but you should have um and uh that's the convex Hull of this three-dimensional shape right but we'll stick to two Dimensions because we'll have to draw things on the board so um let me just uh spec this out a bit uh we're given end points in a plane and those set of points are s x i Yi such that I equals 1 2 to n and we're just going to assume here just to make things easy because we don't want to have segments that are uh uh null or segments that are uh that are a little bit different because they're disc continuous but we're going to assume that no two have the same x coordinate this is just a matter of convenience and no two have the same y-coordinate and then finally no three in a line okay because we want to be able to look at pairs of of points and find these segments and it just gets kind of inconvenient and you have to deal special cases if if no if three of them are on a line and so the convex Hull itself is the smallest polygon containing all points in s and we're going to call that CH of s okay convex Hull of s as small as convex polygon thank you and so just as uh an example on the board when you have something like this you're going to have your convex Hull being that this one is inside of it these two points are inside of it and all of the other ones form the from the hull so we might have p q r s Tu and V and X are inside of the hull they're not they're not part of the specification of CH of s which I haven't quite told you how we're going to specify that but the way we're going to specify that uh is simply by representing it as a sequence of points that are on the boundary on the hull in clockwise order and you can think of this as being a doubly link list in terms of the data structure that you'd use if you coded this up so in this case it would be P to Q to R to S you're going to start with with P in this case it's a w link list so you could conceivably start with anything but that's the the representation of the convex hall right and we're going to use clockwise just because uh we want to be clear um as to what order we're enumerating these points it's going to become important when we do the divide and conquer algorithm so let's say that we didn't care about divide and conquer just for the heck of it and I gave you a bunch of points over here can you think of a simple figet efficiency for just a couple of minutes can you think of a simple algorithm that would generate the segments of the convex Hull for example I do not want to generate this segment VX if I think of a segment as being something that is defined by two points then I don't want to generate the segment X because clearly the segment is not part of the convex Hull but whereas the segment PQ QR RS Etc they're all part of the convex Hull right so what is the obvious Brute Force algorithm forgetting efficiency that given this set of points will generate One By One The segments of the convex Hull anybody did you have your hand up no go ahead yeah draw the line and check how many lines it intersects with um is there I I think you got you draw the line that's good right um well uh but you want to do a little bit more yeah go ahead go ahead yeah ah so that's good that's good that's good all right so uh you know the the first person who who breaks the ice here always gets a frisbe sorry man at least I only hit the lecturer right no liability considerations here okay now now I'm getting scared um so uh right so I think there's a certain amount of when I throw this you know am I going to choke or not right but uh it's going to get harder and one of you guys at the back uh answers a question so you're exactly right and uh you draw a line and then you just look at it and you look at the half plane and if all the points are to one side it is a segment of the convex Hall if it's if if if they're not it's not a segment beautiful right are we done can we go enjoy the good weather outside right no we got a waste to go here right so this is not a segment whereas this one let me draw that little I should draw these in dotted way this is not a segment this is not a segment this is a segment and I violated my rule of these three uh not being in a straight line so I'll move this over here and then that's a segment and so on and so forth okay right I'm sorry oh you're right that's a good point that's an excellent point so what happened here was when I move that out you're exactly right thank you this is good uh and so uh when I when I moved this out here what happened was and I drew this well this one here my convex Hal changed the problem specification changed on me it was it was my fault but then what what would happen of course is as I move this that would become the uh the the segment that was part of the convex Sol okay so sorry to confuse people but what we have here in terms of an algorithm if I leave the points the same Works PR perfectly well right so let me just leave the points the same and just quickly recap which is I'm going to take a pair of points and I'm going to draw and let me just draw this in a dotted fashion first uh and I'm going to say that's the segment now I'm going to take a look at that line and say this breaks up uh uh the plane into two half planes are all the points on one side and if the answer is yes I'm going to go ahead and boom say that is a segment of my convex Hull if the answer is is no like in this case I'm going to drop that segment okay so now let's talk about complexity um let's say that there are end points here and how many segments do I have I have uh order n Square Theta n Square segments and what is the complexity of the test what is the complexity of the test that's associated with once I've drawn the segments deciding whether the segment is going to be a tangent which is part of the convex hall or not what is the complexity o n exactly right so o n test complexity and so we got overall Theta n cubed complexity okay so it makes sense to do divide and conquer if you can do better than this because this is a really simple algorithm right the good news is we will be able to do better than that and now that we have a particular algorithm uh I'm not quite ready to show you that yet um now that we have a particular algorithm we can think about how we can improve things and of course we're going to use uh divide and concer so let's go ahead and do that and so generally with divide and concer as I mentioned before in most cases the division is pretty straightforward and that's the case here as well all the fun is going to be in the merge step right so what we're going to do as you can imagine is we're going to take these points and we're going to break them up right and uh the way we going to break them up is by dividing them into half planes we're going to just draw a line and we're going to say everything to the left of the line is one sub problem everything to the right of the line is another sub problem go off and find the convex Hull for each of the sub problems if you have uh two points you're done obviously it's trivial and at some point you can say I'm just going to deal with Brute Force we can go down to order n cubed if if n is small I can just apply that algorithm so it doesn't have even have to be the base case of n 1 or nals 2 that's a perfectly fine thing to do but you can certainly go with n equals 10 as I mentioned before and run this Brute Force algorithm and so at that point you know that you can get down to small enough size sub problems for which you can find the convex Hall efficiently and uh then you got these two convex Halls right which are clearly on on well two different half planes because that's the way you define them and now you got to merge them right and that's where all the fun is okay so let's just write this out again uh we're going to sort the points by x coordinates and we're going to do this once and for all we don't have to keep sorting here because we're just going to be partitioning based on x coordinates and we can keep splitting based on x coordinates because we want to generate these half planes right so so we can do this once and for all and for the input set s we're going to divide into the left half a and right half B by the x coordinates and then we're going to compute CH of a and CH of B recursively and then we're going to combine so the only difference here from what we had before is the specification of the division um it looks pretty generic it's similar to the Paradigm that I wrote before but I've specified exactly how I'm going to break this up all right um so let's start with uh the merge operation and we're going to spend most of our time specking that and again there's many ways you could do the merge and we want the most efficient way that's obviously going to determine complexity so big question how to merge right so what I have here if I look at the merge step is I've created my two sub problems corresponding to these two half planes and uh what I have here is let's say I have I've generated at this point a convex Hull associated with each of these sub problems okay so what I have here is uh A1 A2 I'm going to go clockwise to specify the the the convex Hull and the other thing that I'm going to do is um in the sub problem case my starting point is going to be for the left sub problem the coordinate that is uh that has the highest x value okay so that's A1 in this case the highest x value going over X is increasing to the right and um in the for the right half of the problem um it's going to be the coordinate that has the lowest x value and I'm going to go clockwise in both of these cases so when you when you see an ordering here associated with the subscripts for these U these points start with uh A1 or B1 and then go clockwise and that's how we number this right so just nutational not nothing profound here so um I got I got these two convex hulls these sub hulls if you will and what I need to do now is merge them together and you can obviously look at this and it's kind of obvious you know what the overall convex Hull is right um so but the but the key thing is I'm going to have to look at um each of the the pairs of points that are associated with this and that and try to to generate the tangents the new tangents that are not part of the sub huls but they're part of the overall Hull right and so in this case uh you can imagine an an algorithm that is going to kind of do what this Brute Force algorithm does uh except that uh it's looking at a point from here and a point from here right so you can imagine that I'm going to do a pairwise a generation of segments I'm going to check to see whether these segments are actually tangents they're part of the overall convex Hull or not okay so what what I would do here is I'd look at this and um is that going to be part of the overall Hall no and precisely why not someone tell me why this segment A1 B1 is not part of the overall Hall yeah go ahead exactly right that's exactly right so here you go um so so that's not part of it uh now if I look at this well same reason that's not part of it in this case and this is a fairly obvious example I'm going to do something that's slightly less obvious in case you get your hopes up that we have this trivial algorithm okay this is looking good right um that's supposed to be a straight line by the way okay um so so A4 B2 I mean that's looking good right because all the points are on one side so A4 B2 is our upper tangent right so our upper tangent is something that we're going to Define as if I look at uh each of these things I'm going to say they have a Yi J okay what is Yi J Yi J is the y coordinate of the of the segment that I'm looking at the i j segment so this yig J is for AI and BJ so what I have here is U y42 out here and this is for the upper tangent Yi J is going to be maximum right because uh uh that's essentially something which would ensure me that there are no points higher than that right so if I go up all the way and I and I find this that has the maximum Yi J that is going to be my upper tangent because because only for that will I have no points ahead of that okay so so y j is upper tangent this is going to be maximum and I'm not going to write this down but it makes sense that um the lower tangent is going to have the lowest Yi J all right are we are are we all good here yeah question okay so good I let me uh the reason we moved out A1 B1 is because if I just drew A1 B1 like this and I'm extrapolating this this is again supposed to be a straight line um then you clearly see that there points on either side of the A1 B1 segment when you look at the overall problem correct you see that on A1 B1 B2 is on this side B3 is on this side if I just extend this line all the way to Infinity in both directions and that violates the requirement that this segment be part of the overall Hull okay that Mak sense good so everybody with me so clearly there is a trivial uh merge algorithm here and uh the trivial merge algorithm is to look at uh every pair of points every a pair right every AI BJ pair and so what is the complexity of uh of of of doing that um if I have n total points the complexity would be which would be n square right because maybe I'd have half here and half there ignore constants and you could say well it's going to be n Square divided by four but you know that's Theta n square right so there's a there's a there's an obvious merge algorithm that is Theta n s looking at all pairs um of points and when I mean all pairs of points I mean I like an A and A B because I want to pick a a pair where I go left of that that dividing line and then right of the dividing line but either way it's Theta and square okay so now you look at that and you go huh you know can I do better what if I just went for the highest a point and the highest B point and I just no that's it I'm done constant time wouldn't that be wonderful yeah wonderful but incorrect okay right so so what is an example and so this is something that I that I I spent a little bit of time uh last night concocting so I'm like you guys too I do my problem set the night before well don't don't do as I do do as I say right um but but I've done this before so that's that's the difference uh but this particular example is is is is new so uh so what I have here is I'm going to show you why there's not a trivial algorithm okay uh that I got to get these uh angles right uh that that you can't just pick the the highest points and uh keep going right and then that would be constant time so that's my a over here and let's assume that I have uh my dividing line like that and then what I'm going to do here and I hope I get this right um is I'm going to have something like like this like that and then I'm going to have B1 here clockwise so B2 B3 and B4 Okay so so as you can see here if I look at U uh A4 uh little adjustment necessary okay so if I look at that um A4 to B1 versus I mean just eyeball it A3 to B1 right is is A4 to B1 going to be the upper tangent no right so so now A3 is lower than A4 you guys see that and and B1 is lower than B2 right so it's clear that if I if I just took A4 to B2 that it would not be an upper tangent everybody see that yep all right good so so what so we kind of have a constant time algorithm we have the Theta n Square in the bag right so you know is there something maybe Theta n how would we do uh this merge and find the upper tangent by being a little smarter about searching for pairs of points that uh will give us this maximum yig J right I mean the goal here is simple it's uh at some level if you looked at the Brute Force I would generate each of these things I'd find the Y J intercepts associated with this line and i' just pick the maximum right and I the constant time algorithm doesn't work the Theta n Square algorithm definitely works but we don't like it so there's something there has to be something in between right so any ideas yeah back there yeah no you're just finding no you're maximizing the yig J so for once you have the segment so that the question was isn't the obvious merge algorithm Theta n cubed right and and my answer is no because uh the Theta n extra Factor was came from the fact that you had to check every point every end point to see on which side of the plane it was whereas here what I'm doing is I got this one line here that is basically y equals Zer if you like right or y equals some uh I'm sorry x equals z or or x equals some value and I just need to once I have the the the equation for the line associated with A4 B1 or A4 B2 I just have to find the intercept of it which is constant time right and then once I find The Intercept of it I I just maximize that intercept to get my Yi J so I'm good okay so it's only Theta n square right good question um so uh so this is actually quite uh very very clever this particular algorithm is called the two-finger algorithm and I do have multiple fingers but uh it's going to work out better if I borrow Eric's finger um and we're going to demonstrate to you the the two-finger algorithm for uh for uh merging these two convex halls and uh then we'll talk about the complexity of it okay and my Innovation again last night was to turn this from a two-finger algorithm not only did I have the bright idea of using Eric I decided was it was going to become the two-finger and string algorithm okay so this is wild this this is my contribution to 046 lore come on right so so the way the two-finger algorithm works and this pseudo code should be incomprehensible okay if you just look at it and you go what right but this demo is going to clear everything up right so here's what you do so now we're going to do a demo of the merge algorithm that uh is uh a clever merge algorithm than the one that uses order n Square time and it's correct um it's going to get you the correct upper tangent and what we're starting at here is with Eric's left finger on A1 which is defined to be the point that's closest to the vertical line that you see here the one that has the highest x coordinate and my finger is on B1 which is the point that has the smallest x coordinate on the right hand side sub Hull and what we do is we compute for the segment A1 B1 we compute Yi J in this case y11 which is The Intercept on the vertical line that you see here that Eric just marked with the Red Dot and um you can look at the pseudo code over on to my uh right if I face the board and what happens now is I'm going to move clockwise and I'm going to go from B1 to B4 and what happened here did the Yi J increase or decrease well as you can see it decreased and so I'm going to go back to B1 and we're not quite done with this step here Eric's going to go counterclockwise over to A4 and we're going to check again yeah keep the string t uh check again whether y increased or decreased and as is clear from here YJ increased so now we move to this point and as of this moment um we think that A4 B1 has the highest yig J but we have a while loop we're going to have to continue with this while loop and now what happens is I'm going to go from B1 counter clockwise again to B4 and when this happens did YJ increase or decrease well it decreased so I'm going to go back to B1 and um Eric now is going to go counterclockwise to A3 and as you can see y31 increased a little bit so we're going to now stop uh this iteration of the algorithm and we're at A3 B1 which we think at this point is our upper tangent but let's check that um start over again on my side B1 to B4 what happened well YJ decreased so I'm going to go back to B1 and then Eric's going to try he's is going counterclockwise he's going to go A3 to A2 and well big decrease in y j now Eric goes back to A3 at this point we've tried both moves my clockwise move and Eric's counterclockwise move my move from B1 to B4 and Eric's move from A3 to A2 so we've converged we're out of the wild Loop A3 B1 for this example is our upper tangent all right you can have your finger back Eric um so the reason this works is because we have a convex Hull here and a convex Hull here we're starting with the points that are closest to each other in terms of A1 being the closest to this vertical line B1 being the closest to this vertical line and we're moving upward in both directions because I went clockwise and Eric went counterclockwise and that's the intuition of why this algorithm Works we're not going to do a formal proof of this algorithm but the monotonicity property corresponding to the convexity of this sub hul and the convexity of this sub hul essentially can give you a formal proof of correctness of this algorithm but as I said we won't cover that in 046 so All That Remains now is to look at our pseudo code which matches the execution that you just saw and talk about the complexity of the pseudo code what is the complexity of this algorithm it's order n right so what has happened here if you look at this while loop is that while I have two counters um I I'm essentially looking at uh two operations per Loop and uh the either one of those counters is guaranteed to increment through the loop and so since I have in this case P points in in one case P plus Q equals n so let's say I had P points here and I have uh Q points here and I got P plus Q let's say equals n uh then I got a Theta n merge simply because I'm going to be running through and incrementing as long as I'm in the loop I'm going to be incrementing uh uh either the I or the J and the maximum that can go to our our our p and Q before I bounce out of the loop or before I rotate around and so that's why this is Theta n um and so you put it all together uh in terms of what the what the merge corresponds to in terms of complexity and put that together with uh with the overall divid and Conquer we have a case where this is looking like a recurrence that you've seen many a Time T of n I've broken it up into two sub problems so I have two and I could certainly choose this uh L over here that's uh that's my line L uh to be such that I have a good partition between the two sets of points right now if I choose L to be all the way on the right hand side then I have this large sub problem makes no sense what whatsoever so what I can do there's nothing that's stopping me when I've sorted these points by the x coordinates to do the division such that there's exactly the same number assuming an even number of points n exactly the same number on the left hand side or the right hand side but I can get that right roughly certainly within one one very easily so that's where the N /2 comes from okay um in the next problem that we'll look at the median finding problem we'll find that trying to get the sub problems to be of roughly equal size is actually a little difficult okay but I want to point out that in this particular case it's easy to get sub problems that are half the size because you've done the sorting and then you just choose the uh the the line the vertical line such that you got a bunch of points that uh on either side and then in terms of the merge operation we have 2 TN /2 plus Theta n people recognize this uh recurrence it's the old merge sort recurrence uh so we did all of this and well it's not merged sort clearly the the algorithm is not merged sort but we got the same recurrence and so this is Theta n log n so a lot better than uh than Theta n Cub okay and uh there's no convex Hol algorithm that's um uh in the general case better than this even the gift wrapping algorithm that I mentioned to you with the right data structures it it gets down to that in terms of theta n log n but uh but no better okay so good uh that's pretty much what I had here uh again like I said happy to answer questions about uh the correctness of the of this Loop algorithm for merge later any other questions associated with this yeah back there uh no you you can't because uh I mean that n log n for the pre sorting I mean there's another Theta n logn for the Sorting at the top level um and we didn't actually use that right so the question was uh can we do better if the input was pre-sorted and I actually did not even use uh the the complexity of the sort we just matched it in this case right so Theta n log n and you can imagine maybe that you could do a Theta n sort if these points were small enough and you rounded them up then you could use a bucket sort or a counting sort and lower that right so this Theta n log n is is kind of fundamental to the divide and conquer algorithm it's the only way you can improve that is by making a merge process that's even faster okay and we uh obviously tried to cook up a Theta one merge process but that didn't work out okay for if you assume certain things about the input uh you absolutely right so one thing you'll discover in in algorithms and in 6046 as well is that we're never satisfied okay so I just said oh you can't do better than Theta n log n but that's in the general case and I think I mentioned that um you you're on the right track if the input is pre-sorted and and uh you can take that away uh well it doesn't help in that particular instance if the you have general settings but uh um if you um the two-dimensional case uh if if if you you know the hull uh all the segments are uh um have a certain characteristic uh not quite pler but uh something that's a little more stringent than that you know you can imagine that you can do improvements I don't know of any compelling uh special case input for convex Hull for which you can do do better than Theta n log n but that's a fine exercise for you which is you know in what cases given some structure on the points can I do better than Theta n log n right so that's something that keeps coming up in the algorithm literature uh if you can use that okay so yeah back there question ah great Point uh and uh you're exactly absolutely right and I just realized that I skipped that step right thank you so much so the question was um how do I remove the lines and it's actually fairly straightforward let's keep this up here uh and uh we don't need this incomprehensible pseudo code right uh so let's let's erase that and uh thank you for asking that question so uh it's it's a little simple cut and paste approach where let's say that uh uh I find the upper tangent um a i BJ okay um and I I find the lower tangent uh let's call it AK BM and uh in this particular instance um what do I have I have A1 A2 A3 A4 uh as being one of my uh sub hulls and then I have B1 B2 B3 B4 as the other one right now what did we determine to be the uh upper tangent was it A3 B1 right A3 B1 so A3 B1 was my upper tangent and uh uh I guess it was A1 A1 B4 um A1 B4 was my lower tangent so so the big question is now that I have found these two um how do I generate the correct representation of the overall convex Hall all right and so it turns out that you have to do this you want and and the complexity of this is important as well and you need to do what's called a cut and paste um that's associated with this where we're going to just look at this and that right so we're going to have these two things and we got to generate a list of points now clearly A4 is not going to be part of that right uh uh A4 is not going to be part of the overall Hull what is it that we want we want something like um A1 A2 A3 um B1 B2 B3 uh B4 right but this this a point that we have to discard here agreed um and so the way we do this is U is is very uh mechanical that's the good news here I mean you don't have to look at it pictorially I just made that up looking at eyeballing it clearly the computer you doesn't have eyeballs right um and so so what we're going to do is we're going to say the first link in general the first link is AI to BJ because that's my upper tangent okay um and in this case it's going to be um A3 B1 okay uh and then I'm going to go down the the b list till till I see um till you see uh BM which is the lower tangent you're on the b list so you're looking for the lower tangent point and and then you're going to jump um till you see BM you link it to AK okay you link it to AK and continue uh till you return to AI right and then you have your your circular list okay so um what you see here is um you have A3 here so I'm going to go ahead and and write out the execution of what I just wrote here so I have A3 and I'm going to go jump over to B1 so I'm going to write down B1 then I'm going to walk along the B's until I get to B4 in this case I'm going to include all of the B's so I got B1 B2 B3 B4 and then I'm going to jump from B4 to A1 because that's part of my um uh lower tangent and I got uh A1 here A2 and uh then I'm back to A3 which is great because then I'm done okay and so exactly what I said happened thank goodness which is we dropped A4 but we kept all the other points all right so answer your question good what is the complexity of cut and paste it's orderan I'm just walking through these lists so there's no hidden complexity here okay good good thank you um you desperately deserve a frisbee in fact you deserve two right where are you I oh could you stand up yeah right two two colors all right oh so well you can give it to him if you like but so uh good thank you so are we done are we done with convex Hall okay good so let's uh let's go on and do median finding I very different very different uh set of uh issues here I still a divid and coner but a very different set of issues the specification here is of course uh straightforward uh you can think of it as I just want a better algorithm than sorting and looking for the median at a particular position n/2 position uh for example let's say n is um n is odd and uh it's floor of n /2 you can find that median right so it's it's pretty easy if you can do sorting uh but we're we're never satisfied with uh uh with using a standard algorithm uh if we think that we can do better than that so the whole game here is going to be I want to find the median a and um I want to do it in better than Theta n log n time okay so that's what median finding is all about we're going to use divide and conquer for this um and so in general um we're going to Define given um a set of n numbers Define rank of X as the numbers in the set that are greater than I'm sorry less than or equal to X I mean you could have defined it differently we're going to go with less than or equal to so in general uh uh the rank of course is U something that you could be used very easily to find the median so if you want to find the element of rank n + 1 divided by two floor that's what we call the lower median and uh n + 1 divided by two ceiling is the upper median and they may be the same if n is odd but that's what we want so you can think of it as not median finding but finding elements with a certain Rank and we want to do this in linear time okay um so we got to apply divide and conquer here and uh as always the template can be instantiated and the devil is in the details of either division or merge and we had uh most of our fun with convex Hull on the merge operation it turns out most of the fun here with respect to median finding is in the Divide okay uh so what I want is the definition of a select routine that takes a set of numbers s and this is the rank so I want a rank I and that I might be n / two uh well floor of n plus one over two whatever um and so what does the divide and conquer look like well the first thing you need do is divide and as of now we're just going to say we're going to pick some element X belonging to S and this choice is going to be crucial but at this point I'm not ready to specify this Choice yet okay so we're going to have to do this cleverly and then what we're going to do is we're going to compute um K which is the rank of X and generate two sub arrays such that I want to find the fifth highest element I want to find the median element I want to find the 10th highest element so I have to I have to keep track of what happens in the sub problems because the the sub problems are going to determine depending on how many elements are inside those sub problems which I can only determine after I've solved those sub problems I'm going to have to collect that information and put it together in the merge operation um so if I want to find the 10th highest element and I've broken it up at relatively arbitrarily it's quite possible that the 10th highest element uh is going to be discovered in the left one or the right one uh and I have to show that it's the 10th highest and it might be that there's four elements in the left and five on the right that are um that are um uh let's see if I Define the rank as less than or equal to X there's four on the left and five on the right that are smaller and that's why this is the 10th highest element uh and that's that's essentially what we have to look at so B and C are going to correspond to um the subarrays that you can uh clearly eliminate one of them uh you can count the number of elements in B count the number of elements in C and uh you can eliminate one of them in this uh in this recursion as you're discovering this uh element with the correct rank in this case I so let me write the rest of this out and U make sure U we're all on the same page uh what I have here pictorially is I've generated B here and C so this is all of B and that's all of C I have K minus one elements here in B and let's say I have n minus K elements in C and uh I'm going to uh essentially um uh take once I've selected a particular element I'm going to look at all of the elements that are less than it and put it into the array B I'm going to look at all the elements that are greater than it let's assume all elements are unique I'm going to put all of them into C and I'm going to recur on B and C that's uh those two are my sub problems uh but what I have to do is once I recur and I've discovered the the ranks of the sub problems I have to put them together so what I have here is if k equals I if I've computed the rank and I I realize that if k equals equals I I should say uh if k equals I then I'm going to just return X I'm done at this point I got lucky I picked an element X and it magically ended up having the correct rank okay uh not always going to happen uh and so in other case if K is greater than I then I'm going to return select bi I so uh what I've done here is uh I'm if if K is is greater than I then I'm going to say oh so now I'm going to have to find the element in B I know that it's going to be in B Because K is greater than I and I got to find the exact position depending on what what i is over here but it's going to be you know somewhere between um between one and K minus one okay and then uh the last case is um if uh K is less than I then uh this is a little more tricky I'm going to return C of I minus K okay so what what happens here is that um my K uh is uh that the the rank for the X that I've looked at over here is less than I so I'm going to look I know that I'm going to find this element that I'm looking for in C but if I just look at c um I don't want to look at C and look for an element of rank I within C right that that doesn't make sense because I'm looking for an element of rank I in the overall array that was given to me so I have to subtract out uh the K elements uh that correspond to X and all of the K minus one elements that are in B to go figure out exactly what position or rank I'm looking for in the subarray corresponding to see okay so people buy that so that's just a small little thing that you have to keep in mind as you do this right so that's uh pretty straightforward looking pretty good uh and you say well am I done here and uh as you can imagine the answer is no because we haven't specified uh this this value now can someone tell me um at least from an efficiency standpoint um what might happen what we're looking for here as you can imagine we want to improve on Theta n log n and so you you could say well I'm happy with Theta n Theta n a Theta n complexity algorithm is better than a Theta n log n complexity algorithm which is kind of in the bag because we know how to sort and we know how to Index right so we want a Theta n algorithm now if you take this and um if I just uh I picked let's say the the the biggest element or I I kept picking X to be n or n n minus one or just pick a constant value I picked X to be in the middle right I picked the index uh uh because I can always pick a pick an element based on its index I can always go for the middle one right so what is the worst case complexity of this algorithm for uh if I don't specify or I give you this arbitrary selection corresponding to X belonging to S what is the worst case comp complexity of this algorithm right yeah go ahead n Square why is that yeah exactly right that's exactly right um so what happens here is that you're doing a bunch of work here with is Theta n work right right here this is Theta n work okay so given that you're doing Theta n work here uh uh you have to be really careful um as to how you pick the the the X element so what might happen is that you end up picking the X over here and uh given the particular rank you're looking for you have to now you're left with a large array that has n minus one elements in the worst case you started with n you do not go to n /2 n n /2 which is what divide and conquer is all about or even n / B okay you went to n minus one and then you go to n minus 2 then you go to n minus 3 because you're constantly picking this is worst case analysis you're constantly picking these subarrays to be extremely unbalanced right so when the sub arrays are extremely unbalanced you're you end up doing Theta n work in each level of the recursion and those Theta NS because you're going down all the way to from n to one are going to be Theta n Square when you keep doing that okay so uh good thanks for that analysis and so this is Theta n s if you uh if you have a bad selection okay so we will talk about randomized algorithms uh but the problem with randomized algorithms is that um the analysis will be uh given a probability distribution uh uh and it'll be expected time what we want here is a deterministic algorithm that is guaranteed to run in worse case Theta n right so we want a deterministic way of picking X belonging to S such that um all of this works out and when we get our recurrence and we solve it somehow magically we're getting fairly balanced partitions fairly balanced sub problems in the sense that it's not n minus one and one it's something like it could even be n / 10 and 9 N / 10 but as long as you guarantee that you are shrinking things down geometrically and the asymptotics is going to work out okay but that's the determinism is what we need um and so um we're going to pick X cleverly right and um we don't want the rank X to be extreme so this is uh not the only way you could do it uh but this is really very clever this deterministic way and you're going to see some constants here and we'll we'll talk about them once I've described it but what we're going to do is we're going to arrange s into Columns of size five right we're going to take this uh single array and we're going to make it a two-dimensional array where um the number of rows is five and the number of columns that you have is n over five uh ceiling in this case um and then we're going to sort each column big elements on top and we're going to do this in linear time and you might say you know how did that happen well there's only five elements so it's linear right um you could do whatever you wanted you know you could do n raised to 4 but it's 5 rais to 4 and it's constants don't you love Theory um so then we're going to find what we're going to call the median of medians so I'm going to explain this this works for arbitrary rank but it's a little easier to focus in on the median to just explain the particular example because as you can see there's some uh intricacy here um associated with the uh with with the breakup and so here we go I'm going to draw out a picture and you're going to try and argue that this deterministic strategy that I'll specify gives you fairly balanced partitions in all cases okay so what we see here is we see pictorially you see Columns of length five right each of these dots corresponds to a number this one-dimensional array got turned into a two-dimensional array right so I got four full columns and it's certainly possible given n that my fifth column uh is not full right so that's certainly possible so that's why I have that up here um so what I have here is I'm going to lay them out this way and I'm going to look at that I'm going to look at the middle elements of each of these n over five columns right that's exactly what I'm going to look at um now if I look at what I want what I want over here is this x if I want to find uh um I'm going to find the median of medians so uh this is uh is is is is is X now it it is true the first that uh um these columns I'm just putting that up here imagining that that's X it's not guaranteed to be X because the columns themselves uh aren't U uh the well each of these columns is sorted and uh what I'm going to have to guarantee of course is that when I go uh find this median of medians um is that it ends up being something that gives me balanced partitions right so let me say a little bit more before I explain what's going on um each of these columns is sorted and uh s is arranged into Columns of of size five like I just said here um the these are the medians okay um if I look at if if I look at determining the medians and I say that once I've determined this x which I've discovered that it's the median then uh this is right there in the middle there's going to be a bunch of columns to the left of it bunch of elements to the left of it and a bunch of elements to the right of it and in this case I have five columns I could have had more uh it happens to be the third one so the idea is that once I find this median of medians which corresponds to this x number I can I can say that um all of the columns these are all uh uh correspond to columns that have their median element greater than x these correspond to columns that have their median element less than x okay so what I have here in this picture is that these elements here are going to be greater than x okay and these elements here not that are going to be less than x right so let me be clear what's happened here is we've not only sorted all of the columns such that you have larger elements up here each of these five columns has been sorted that way on top of that I've discovered the particular column that corresponds to the median of of medians and and this is my X over here and it may be the case that you know these columns aren't sorted this one may be larger than that or vice versa same thing over there I have no idea but it's guaranteed that once I find this median that that I I do know uh all of the columns that have elements uh that uh in this position that are uh less than this X and I know columns uh that uh in this position have elements that are greater than x okay y you're exactly right I would have probably been able to U get the same asmic complexity if I dropped those because I had a constant number but you're absolutely exactly right right so the point that uh the question was I I just redrew it these two are clearly less than x as well because they're part of the Sorting right um and I that's essentially what I have here now my goal here and you can kind of see from here as to where we headed right what I've done here by this process of sorting each column and finding the median of medians is that I found this median of medians such that there's a bunch of columns on the left and and roughly half of those elements in those columns are less than x and then there are a bunch of columns on the right and roughly you know half of those columns have have elements that are greater than x um so what I now have to do is to do a little bit of math to show you exactly what the recurrences and let me do that over here so that's the last thing that we have to do um I probably won't solve the recurrence but that can wait till tomorrow that recurrence will be U something that's uh not not particularly difficult to to solve so I want to now make a a more quantitative argument that uh the variable being n as to how how many elements are guaranteed to be greater than x and essentially what I'm saying which is I'm writing out what I have on that picture there half of the N over five groups contribute at least three elements greater than x except for one group with possibly less than uh five elements which is the one that I have all the way to the right and one group um that contains X so for all the other columns I'm going to get three elements that are greater than x um and so if you write that out this says there at least three n / 10 because I have half of all of those groups minus 2 and I'm not counting uh perfectly accurately here but I I have an at least so this should should all be fine 3 n / 10 uh 3 * n / 10 minus 2 elements are strictly greater than x right and that comes from that picture um I'm going to be able to say the same thing um for less than x as well I can't count the one uh uh depending on how things go maybe I could have uh played around and and subtracted a one instead of a two in the latter case but I'm just being conservative here it is clear that uh I'm going to have a bunch of columns that are full columns uh that have going to be contributing three elements that are greater than x and in this case I have well two of them here for the less than x and I got uh one for the greater than x right so that's all that I'm saying over here with respect to the balance of the partitions and it turns out that's enough H it it turns out um all I have to do with this observation is to go off and write the recurrence and uh we're going to get uh a an efficient algorithm yeah not or equal um no there's nothing that's equal yeah all unique yeah yeah I I assume that so convenience yeah there's always a little bit of convenience thrown in here uh we will assume that uh that the the array is is uh has unique elements so there's nothing that's X okay good um so uh the recurrence once you do that um is T of n equals we're going to just say it's order one for n less than or equal to 140 where did that come from well I like 140 uh it's it's just a large number uh it it came from the fact that you're going to see uh 10 minus 3 which is 7 and then you want to multiply that by two so some reasonably large number we're going to go off and we're going to assume that's a constant so you could sort those 140 numbers and find the median or whatever rank uh it's all constant time once you get down to the base case right so you just want it to be large enough such that you can break it up and you have something interesting going on with respect to the number of columns right so don't worry too much about that number uh the the key thing here is the recurrence right and this is what we have to spend the rest of our time on and um I'll just write this out and explain where these these numbers came from all right so um that's our recurrence uh if for n less than or equal to 140 and else you're going to do do this so what is going on here what are all of these components SC responding to this recurrence um really quickly this is um simply something that says I'm finding the median of medians I'm finding some element that has a certain rank so this median of medians is going to be running on N over five columns so I'm going these are there there n over five columns here and I'm going to be calling this algorithm uh recursively the median finding algorithm uh to to do that finding the median of medians okay um this thing over here is uh I'm going to be discarding at least depending regardless of what I do because I have these two statements here um I take the overall uh n and I'm going to discard uh in my uh Paradigm over here I'm either going to go with b or I'm either going to go with C depending on what I'm looking for uh and given that B and C are not completely unbalanced I'm going to be discarding um 3 n / 10us six elements which simply corresponds to me ignoring the ceiling here and multiplying the three out so that's 3 n / 10 - 6 so then I have 7n / 10 + 6 that's the maximum size uh partition that I'm going to recur on it's only going to be exactly one of them as you can see from that it's either else it's not recurring on both of them is recurring on one of them so that's where the 7n / 10 + 6 comes from and then you ask where does this Theta n come from well the Theta n comes from the fact that I do have to do some sorting it's constant time sorting for every column okay because there's only five elements so I'm going to do constant time sorting but there's order n columns right because there that it's n/ five columns so this is the Sorting of all of the columns all right so that's it and I'll just leave you with um you cannot apply the master theorem uh for solving this particular recurrence but if you make the observation and you'll see this in section you make the observation that n / 5 + 7n / 10 is actually less than n right so you get you know 2 N here and 7 n there that's actually less than n this thing runs in linear time and you'll see that in in section tomorrow so this whole thing is Theta n time see you next time