Video 3-9: §3.7 Order statistics, quickselect, median of medians

0:00 Divide and conquer overview

0:05 in this in this last part of unit three we'll talk about this design principle for algorithms divide and conquer a little bit more outside of the narrow context of sorting where we've seen it again some uh some really basic fundamental questions that we will tackle and it will be just a brief Glimpse at it but I think these are these are worth knowing and it's helpful to keep in mind if you design algorithms there are certain principles that work across different algorithms and dividing conquerors one you may have if you had an undergraduate algorithms class you may have seen others there's there's greedy algorithms there's branch and Bound for optimization problems and dynamic programming is another big one we'll only really talk about dividing concrete here because that fits well into uh into the topics we discuss anyways if you want to learn a bit more about this and you're eligible for this there's a follow-up module on on Advanced algorithmic Techniques in the second semester for here we'll keep it with divide and conquer and you've actually seen this before we uh we pointed I pointed this out for both quicksort and merge sort so um let's see where this comes from the the name just comes from this this Latin phrase that at least Julius Caesar

1:30 was using and many other people used uh like uh one one definition from from a dictionary for dividing Congress to make a group of people disagree and fight each other so that they will not join against you I guess you see this in in politics in in many ways it's not exactly the nicest way to proceed uh it seems effective though sadly or as a matter of fact uh for algorithms it's much less controversial I think often it's it's just a little a cheeky piece of terminology you'll find this in algorithms often that people think it's funny to call things that provoke provoke associations to other fields and sometimes it's helpful just to build a metaphor and sometimes it's uh just a little silly I'll leave it to you if you uh which which category this one is but the computer science perspective question

3:00 yeah I agree so uh the uh the comment was that binary search might not be the cleanest uh example I'll come back to this uh I I agree and disagree in a way it's it's okay it's a soft definition right this is not a mathematical definition it's it's a vague thing and so we can live with both agreeing and disagreeing in a sense uh what I would say in computer science what what is dividing conquer for us for algorithms is some some method that breaks things into smaller parts and you can recursively solve those usually we think of these recursive parts of non-overlapping in some in some sense and there must be a way to assemble the solution for the entire problem from the solution of the sub problems I think undeniable examples are merged sword in quicksort where you do exactly that you uh merge sword is the most classic one the the poster child of divide and conquer you cut exactly in half you have two equal problems you recursively solve those and then there's a bit of um of a step afterwards merging them to get the solution for the entire problem quicksort is slightly different you spend a little more time before you recurse and after the recursion actually nothing needs to be done

4:17 binary search in a way is not the cleanest dividing concrete because you only really solve one of the sub problems uh in a way I would still say it can be can be classed as this you uh you break the problem into two parts and then you discover that you only need to solve one of them eyes as I said I was maybe similar for towers of Hanoi uh you kind of use a solution for sub problems twice it's still in a way breaking the problem into smaller pieces I think the exact boundaries of this are super vague so don't don't get too obsessed with the term it's more if you're if you have to solve a new algorithmic problem take it as inspiration maybe something dividing conquery works and if it does great then you solve the problem and if what comes out is not the nicest cleanest example of divide and conquer who cares you solve the problem

5:24 I just want to show you a few other examples and um actually one of them will be of the binary search type so you might might disagree again that this is maybe not dividing Concrete in the cleanest form

5:38 Introduction to order stats

5:40 the first part I want to show you is order statistics so that's a another classical comparison based problem and let me motivate this a little bit before I show you what the concrete problem is uh if you if you do some data science task you have numerical data yeah a lot of it and uh you would like to see a quick summary uh what does this data look like a standard thing and it's so standard that pandas this this python library for data science has actually a a simple call for this I think it's called describe on a date of on a data sequence or data frame column so it's this uh is something that people do a lot if you have a lot of numerical data and you'd like to have a concise summary of what is it like a standard thing is to do all of these and look at those together you want to compute the mean so the average value and the standard deviation to have an some feeling of where where's the data on average I guess and how much does it deviate from that uh you may also want the minimum and maximum to have some more tight bounds on the Range so what's the uh the outliers if you like where are they

6:57 you can have a little closer look with a histogram if you know the range you can break the range up into say 10 pieces and look how many of the data points lie in each of these 10 pieces then you get a histogram and then the last bit that people often like as well is uh quantiles or as the special cases the median which is the value so that half of the data is smaller and half of the data is bigger and quartiles is the same with it's a point where a quarter of the data is smaller and three quarters is bigger or the symmetric version the the third quartile where you have three quarters smaller one quarter bigger that just gives you another angle of seeing whether where the range is for the majority of the data right that's that's what um what the describe function usually shows here in pandas and what often helps you to just see uh a rough picture of of the entire data you may have seen uh these box plots uh whisker box whisker charts they are all variations of that so the question is how can we compute this if you wanted to implement such a function the describe function you you start thinking about how to compute all

8:15 these and it turns out for the first three it's quite easy to do in a linear scan over the data in one way or another um okay maybe for standard deviation you have to think a little bit uh but there's formulas to do it even in online mode you can add one point at a time and you can keep a current a running standard deviation it's trivial for the mean almost but you can do it for standard deviation as well and for the others is also easy but there's the fourth one ways maybe not so clear if you can do it in linear time

8:57 uh this this fourth uh Computing computing quantiles now uh okay let me first formally Define what the problem is in the general case I call this finding order statistics so these these guys are called order statistics because they're statistics from the data summary points of the data that depend on the order only and the algorithmic problem I called it selection by rank sometimes is also just called selection but that's it's a bit unspecific what you really have is you want the so and so smallest data item that's why uh what what we called rank before so you give it an array of numbers and a number K an index in that array if you like and the goal is to find the value that goes into this position if the whole array was sorted now we could obviously solve this problem by just sorting the entire array and we've seen many methods to do that and maybe the array is partially sorted right then you could even take advantage of that as I've shown you last last week but there's also a way to avoid sorting all together at least most of it some special cases for K is the things we mentioned before it actually generalizes Min and Max as well which is Nifty

10:23 uh which also shows you for minimum and maximum the problem is very easy a linear scan is enough you just keep the current minimum whereas for the general K version if you if you want the median it seems less clear how to do this without sorting all right question

10:57 all right um I should have put a slider question here on on how many people have seen this already I guess quite a few will have uh as always in this class I guess it's a rough it's roughly two uh two-thirds so I've seen it and a third is puzzled so same same problem as always but let me show you a solution

11:23 Quick select algorithm

11:25 and the solution goes by the name of quick select anyone remembers quick selects the quick slido free version who remembers quick select quick hands who has never heard quick select

11:44 and the the remaining 90 uh are unsure so it's it's a classical algorithm um and you'll you'll like it once you've remembered it the key observation is if we if we have an element It's relatively easy to find its rank you can just take the element compare it to all the others and count how many were smaller that's the rank if you have a rank and want to find the element that has this rank that's a little less clear how to do it but you can take this easy task and move your way through until you found something well okay that explanation wasn't too great uh what you do is you pick an arbitrary element and you find its rank suppose that rank is J what you wanted was the rank k there's really just three possible cases now if you found exactly by chance you picked an element and it was the one you were looking for uh lucky you and you're done not usually the case so if if the element you found is smaller its rank is smaller than k you still learn something because all the elements that are even smaller than this element are definitely not the element of rank k this one was already too small the others are even smaller so uh throw them

13:09 away and similarly if the element you found is larger in rank than the element you're looking for all the elements that are even larger are not needed anymore so far so good

13:26 now how can we make make use of that uh is this really really something we've solved already taking an element and finding its rank we call this partitioning in quicksort but it's actually the same thing quicksort pick the pivots and found for every element is a smaller or larger and it returned the rank it returned the position of the pivot now the partition function has the nice side effect that it doesn't just find the rank it also changes the array so that everything smaller is on the left everything bigger is on the right and that's convenient because to do this elimination step we don't just want to know that we can illuminate some elements we want to know which ones right so what we do in in terms of code is is exactly that spelled out we choose our pivot as before and uh there's an asterisk to ask before that we'll come back to but suppose for now we just pick some random element as our pivot we do the partitioning step and that comes back with the rank of the chosen element we have no control over J really but we can distinguish the cases we could be lucky then we return it or we could have an element that's too small in rank remember too small means

14:48 everything that's even smaller can be thrown away so we can recurse on just the elements that are larger which is the right part of the array and so the only bit here the tricky bit is you have to adjust the rank you're looking for if you were looking for the case in the entire array if you now throw away some small elements you have to just subtract the number of elements you threw away and that's that's what What's Happening Here I guess it would have been nicer to write K minus J plus 1 in parenthesis of course the same thing and the other case if the element you found is too big then you throw away all the even bigger ones so you recurs on the left part in this case the rank stays okay

15:44 and that's that's quick select notice that it's quite similar to quicksort hence the name but it only recurses on one side you never need to go on both sides because you're only looking for a single element which can either left be to the left or to the right of the pivot okay because of that because you only have a single recursive call you can rewrite the code to just uh avoid the recursion and make one big loop out of it if you've seen similar things that's not too surprising that's that's usually the way you want to implement it because it's more efficient but just for presenting the code I think this is easier

16:34 how good is quick select and the form I've shown and shown to you now unfortunately the worst case is really poor and this the reason is just the same as in quicksort you could get repeatedly unlucky by always picking as pivot the element that's largest suppose for the sake of the argument you're looking for the minimum in the array and you call Quick select for that which is not what you should do but suppose well if if you implement the library functions users will call it even with nonsensical arguments get used to it so suppose you try to find the minimum and you always get the maximum as the pivot then you always exclude just a single element and you spend linear time in partitioning each time so you get this quadratic worst case again is the same argument as in quicksort and that's terrible however you can prove that this is kind of an isolated unlucky case most of the time in a similar senses for quicksort on average and more you only need linear time and linear time is probably the best you can hope for because even if I gave the element to you just to check that this actually has rank K would take you linear time so there's no way to get it faster

17:57 uh what's what's nice is we don't need any extra space not even the recursion stack if you get rid of the recursion um you can tweak this same idea to find more than a single uh order statistic in one go the reason I'm listing this here is if you do a box plot you want to find the median and the lower and upper quartile you could call Quick select three times that's fine you can also modify the code to find those three in one go which is a slightly a slight bit faster so if you do this many times it might be worthwhile doing so I listed it as a positive because quick select makes this fairly easy um it's not not relevant for the module to know exactly the details foreign

18:55 I've used these two personas um a lot in the next chapter so here they they already come up this is the programmer who is the the practitioner's point of view which really says I'm using quick sword to sort all the time I might as well just use Quick select for finding order statistics is probably more likely that some someone uh some sunstorm flips bits in your memory then that you see this quadratic worst case uh whereas this guy is the theoretician who is interested in the internal truths and the worst case things and so on uh and he's uh he's worried about uh this worst case and so it's as an academic question for sure and maybe for security reasons sometimes as well in practice it might be worth knowing if you can do it in worst case linear time this gave us only expected linear time okay we can do worst case n log n by sorting that's at least close but that's a bit lame I guess uh the repetition won't be happy

20:10 okay if you need multiple order statistics I think the question is how many if it's a constant number say three uh three times linear is still linear it's still better to do that as opposed to sorting if you need a lot of them I guess log in right then uh then there's a point for for sorting if you're smart if you this is this is really tough to quantify however if you run quick select it will make the array slightly sorted because it partitions at some points and it leaves that as such so you can if you remember the pivot Points that you already had then you can try to speed up future calls to Quick select so that you never do more than this full sorting work but you can do just as much as you need it organically that's a okay that's a side remark like again it's a Nifty thing you can do um well won't be on the exam if that's what you want to hear

21:29 Median of medians method

21:31 now coming back to this question can you do it in worst case linear time the answer is uh yes we can do it um what we need is better pivots to avoid this worst case so far so obvious for example if the pivot we got was the exact median all the time we'd be fine because we would cut the remaining number of elements in half in each step at least maybe we're even lucky and get the element we're looking for earlier but we definitely get away uh with we would get rid of half the elements each time and um

22:15 that's uh okay I wanted to show this picture first uh suppose we could get rid of a constant fraction each each time and this picture is for getting rid of half of the elements each time it's a visual proof for the fact that the geometric series converges to a constant but if you're more visually inclined one times n that's the starting State you have all the elements you cut it down to one half in the first step then you cut it down to a quarter to an eighth and so on that's why you follow this spiral in and you see you always have enough space to fit the next one half in the remaining little bit so the overall box that you need is just two times the starting point

23:09 I think this picture is is more valuable than quantifying this more more precisely whenever you design algorithms if you can somehow make it so that the recursive call is on just

23:25 0.9 the number of elements that you had before and you don't spend more than linear time for each step your overall cost will be linear and this is the the visual proof for that if you don't have a factor one half you get a different constant than two

23:48 yeah foreign yeah if you spell if you write this down uh it would be some geometric series of this type you would normally stop at some end but you might as well extend it to Infinity

24:07 and in this case that's two and if you have some other Factor here sorry if I put this um if I put this Alpha here the general is 1 over 1 minus Alpha so you can can work that out

24:38 so that's kind of the visual proof if we had in each case the median as our pivot we'd be fine but of course that's uh not not too helpful if we're trying to design an algorithm to find the median in the first place we already need our own solution and in this case recursion doesn't save us because it would be recursing on the very same problem I want to find the median of these n elements oh I can do a quick select I'll just find the median of these n elements quickly and then oh hold on right so it doesn't help us you would recurse on the very same problem

25:18 but if we could do something like this that would be good and this remark says it doesn't have to be the exact median as long as you can guarantee it's a in graphical speak so

25:31 as long as you can guarantee that the pivot is in here and this part is Epsilon times n for a fixed constant Epsilon then that's enough for this kind of argument to go through so can we somehow do this can we find not the exact median cheaply but somehow something not too far away from it

26:02 and it turns out we can it's a little a little more convoluted some the idea is uh we split the elements up into groups of five and from these five elements we just sort those and we take the middle one

26:27 five five is the smallest constant so that this works you can do a slightly larger one uh that's the smallest where it goes through where you can make it you can do it with 17 if you prefer

26:51 the middle one out of five and uh on that you recurse so let me go a little slower this code basically does this split the elements into groups of five so there's a loop M will be the number of Pfeiffer groups and that might be one one left over where we don't have five elements right uh for each of these groups of five we we sort these five elements so that's just a tiny section of the array we sort this with whatever method I don't care too much at this point uh it's so it's only affecting the constant Factor at the end so you can can be smart about this and then we take the middle one so five I plus two that's this this black guy and we swap it to the beginning of the array that's just to keep all these middle ones together so I'll take these um and put them at the beginning of the array and all the others are behind that okay

28:00 and then I'm calling the quick select algorithm recursively on this bit and find the median now that is again something like we're using ourself but this time on a smaller problem and that's why it's going to work at the end it's a problem that has at most every Fifth Element okay amazingly the rest of the algorithm is unchanged uh instead of picking some random pivot we call this function which chooses the median of this prefix

28:38 and then the rest is as in quick select we use that as in pivot we partition and we do what we've done before the amazing bit is that this is good enough and that it's linear time

28:54 Analysis and refinements

28:57 let me point out that this is um that this is a mutually recursive function now we have two functions and they both call each other this one calls choose pivot and this one calls that one again so it's not visible from just looking at the at the lower function but we actually have two recursive calls the first one from choosing the pivot and then later from the main the main recursion okay so the first recursive call has at most n over five elements that's just by choice so that was the that's the easy one to analyze

29:41 for the second recursive call we'll have to work a little harder to see on how many elements it can in the worst case work uh here's here's the picture I started drawing uh slightly more nicely so these are our groups of five and there might be one group left over from all the groups of five that are complete we take this middle element and from all those middle elements we select the median that's why the algorithm is called median of medians algorithm so here's here's our median and notice that if if you have an even number of elements you have to break ties there's actually two elements that could count as a median I'm choosing the smaller one arbitrarily that's why it's rounding down here so this m that's the pivot element that's the one that determines how we partition and how we recurse now how many elements can in the worst case be in this recursive call in either of these recursive calls and for that you have to look at these shaded areas

30:50 we know that all the elements above the median in the five are smaller than the black one the middle one because they're sorted so in each column the two topmosts are smaller than the middle one we also know that these are all smaller than this median because that's the median so if we arrange them in sorted order of these middle elements then

31:19 okay zooming too fast is dangerous but it worked so this is smaller than the median this is smaller than median this is smaller than the median which means transitively these are all smaller than the median and these and these and these two anyways because it's in its column okay

31:40 so we can in each recursive call we either get rid of this blob of elements or of this blob and the smaller is is this top this is left upper one so how many elements are in there roughly it's half of each uh so it's half of the columns because it's the median and in each column we get rid of three elements so it works out to 3 over 10 as a fraction of all elements

32:22 and if you use this in a recursion for the cost so you can write C of n as the overall cost for the algorithm again in some abstract cost measure you have a linear term for the partitioning that's that's this call and you have the two recursive calls um you're using the the worst case size question

33:01 so if we use the larger number if we make the columns taller more than five elements I don't think that this this part improves much uh so the the red blob actually gets smaller but the recursive call up here gets smaller because you're just recursing on every 17th element instead of every fifth uh but you have to balance it out with the Sorting cost for each column which can which grows so uh as long as you keep The Columns of constant size it only affects the overall constant and there's there's some trade-off the original paper where the um well the researchers proposed this algorithm they tried to optimize for this this size of the column I think it was there was something around a dozen elements worked out best but that depends on the Assumption of the cost uh there's different types of costs you have to trade against each other if you stay with the five elements then you're left with this recurrence and uh a simple way to argue why this is linear is uh just to just start with the assumption that the cost is linear and then proof that this is a correct solution the details are a bit more messy and so I left those out but you can you can formally prove that

34:32 this recurrence is upper bounded by some recurrence like this so you have linear cost for the partitioning and you have recursion on total size ninety percent of what you had and remember from the last slide that's that's good enough to guarantee overall linear time as long as you can have a constant strictly less than one uh you get linear time and so that's that's worst case so uh human theoreticians happy now

35:13 uh I I can mention that there's an intermediate version between those two extremes picking some arbitrary pivots and picking this really really good one where you can guarantee that it excludes a fixed fraction of the elements uh where you just you take a larger sample of the elements and pick the median from there but you you use a much smaller set than every Fifth Element you can pick something like square root elements from the randomly chosen from the array and find the median from there then uh theoretically speaking in the worst case you're still quadratic or close to it but you're even even less likely to ever see a bad run time and you can you can improve the expected case further

36:09 you can still uh so the question is why why is it still quadratic if you use such a large sample I guess you can still have the largest element in the sample so say the sample is the square root and largest elements so you would just exclude square root and elements but you're left with n minus square root n which is by and large not much better than n

36:36 okay so much for this that's uh still an application of dividing conquer but a little more sophisticated in in the way they interact it's no longer just splitting in half