Video 3-8: §3.8 Further divide & conquer algorithms

0:00 Introduction to puzzles

0:03 in the last section of this this Parton Dynamic on divide and conquer algorithms I want to show you just very briefly two other examples where uh you can use divide and conquer but we won't go into much detail this is basically just teaser what's possible uh but it's it's two more cute problems um which maybe uh you enjoy as puzzles um even if we don't do them in detail the first one is the majority problem so new problem time to wake up again uh you're given an array of objects and um your task is to find if it exists an object that occurs more than half of the time so a simple majority in in political terms but uh it may not exist right you may have elements where there's too many different elements and no no one is in the majority but if there is an element in the majority you're supposed to report

0:28 The majority problem

1:08 it let's see what we can do without much uh sophistication you can go through the array and try every element and check if it is a majority uh how do you do this check well you compare it with every other element and keep account of how often it came out equal so it's just count the number of Chase so that AI was equal to

1:39 AJ well and if if that count is bigger than n half then it is a majority and maybe stating the obvious if you have one majority that you found you can stop because there can only be one majority right it's more than half of the elements so there can't be more than one of those the algorithm is still not so great because in the wor case it might need n Square time uh in particular if you have an input where you don't have a majority you have to keep going until you tried every element to prove that there is no majority okay so even if your output is just no there is none a correct algorithm is supposed to have a implicitly proven that that's correct so it can't just uh say no and and keep fingers crossed good so that uh that's the the obvious one

2:31 Divide and conquer solution

2:33 there's various ways how we can do better if you never thought about this problem it's it's kind of a shame I I feel uh I feel with you that I'm spoiling it before I've given you a fair chance to think about it um but there's many other problems for you to think about so uh I can point you to more let's try to apply the divide and conquer approach to this and the reasoning is suppose this array has a majority well then it's present in more than half of the positions that means if I um if I look at the halves of a if I just cut them in the middle merge sword style if there's n half elements uh at least n half positions where there's majority occurs they must be somewhere right so it has to be the majority in either the left or the right side or maybe even in both there's just not enough enough places to hide it otherwise so in the in the worst case you have an equal split say roughly uh N4 and N4 +

3:48 1 but then it would be a majority in this right part so uh it's worth pointing out majority means strictly more than n half it's not good enough if you're you have an option that's half the people it must be half plus one good so that's the observation if if there's a majority then I can cut the array in in two parts and if there's a majority in the overall thing it's the majority of the left part or the majority of the right part and they could turn out equal if both of these parts don't have a majority uh I don't yeah then uh have to think about it probably so um we recurse on the left and the right half and that comes back with some candidate so what are the

4:55 options so we can have from the left we can either have some some value X or it says there is no majority and from the right we can have a value y or not a

5:16 majority if either of the two says None uh if if both say none then there's no majority overall by this by this okay right As proved by contradiction if there wasn't overall majority then it would have been the majority in either the left or the right side at least so if both are none we just return none and otherwise we have a candidate or

6:12 so uh the check is again as before we compare it with every other elements but we're only doing this with at most two elements now two candidates so that has linear time and if you write down the recursion you'll see it's exactly as in merge sord so the overall cost for this in the worst case we'll have to do the recursion on the left and the right side so I'm assuming that things work out nicely and we don't have to round so assuming N is a power of two then we have two recursive calls on half the size and we add something that's linear in N from checking the candidates and that's precisely the shape that we've had for merge sort and so the solution is is of the same order of magnitude again I want to stress this many more times n log n and n squ if you just look at the functions maybe it doesn't seem like a big deal but it's a huge deal n squ is so much slower than n log n in most cases all

7:21 Linear time voting algorithm

7:23 right now it turns out in this case you can do much much better if you just row divide and conquer overboard so this is an algorithm that doesn't actually have any justification to be in this unit it's not about sorting and it's not about dividing conqur but it's so cute and cool that I want to show it anyways uh and it's it has a nice analogy I'll come back to that to these two guys it's the following algorithm um you start out with some candidate for the majority but initially you have no idea so you just set arbitrarily this to some value sorry X is the X the candidate C is a counter you start with a counter zero and you don't have a candidate um if the counter is currently zero then you take the next element that you're looking at and say ah maybe this is my majority and you said I've seen that once from now on if the counter is not already zero so you have some candidate from before and you've seen it a certain number of times s then you update the count either if the element is occurring again you increment the counter but if it's a different element you you decrement it okay and the claim is once this has done

8:48 it will always return an element it always returns x uh so that's a candidate for the majority but it may not be the majority you need another check for one element

9:04 okay that's this part but the cool thing is uh if that if that procedure gives you something and it's not a majority there is no majority and uh the reason to see this is um where these two guys come in you you can imagine uh there's a fight of different different parties and they fight in duels and whenever they Whenever two people meet they have a gunfight and they actually both die it's a gruesome gruesome world so what you do here is uh ax is your your current leader of the underworld um and if uh someone else comes along and they're from the same gang they just join join the fighting group but if it's someone else they have a duel and they both die and uh if you ever reach the point that nobody's currently staking the claim then whoever comes next becomes the current current leader now if you have a majority there will always be one from that gang standing after the duels that's the part that you have to prove for this one again it's not really about divide and conquer so I feel it's a bit it's a bit outside of outside of this thing but it's such a cute algorithm that I wanted to show it but again this is this is for fun for you

10:32 don't uh uh we don't have to obsess about it too much very briefly on the second example second of the other dividing conqueror problems um and for this one I'll leave it with the claim this is something that sometimes you do in some in some algorithms classes there a bit of a more advanced thing so I just want to show show you that you can do more fancy things with divide and conquer but we we won't do the details uh but I want to define the problem so this time it's not just numbers but it's points in the plane so two dimensional points you're given a list of those points and they each have an X and a y coordinate that's how they're cartisian coordinates okay and your task is to find two of those points that are closest in in St distance idian distance

10:41 Closest pair of points

11:37 okay you can imagine how this could be a useful useful problem in various applications where I don't know the points could be things on the map or you you can cook up various things where this pops up as a as a sub problem um the naive solution would be look at every pair of points compute the distance and um keep track of the minimum that you've seen over over the old whole point of the whole course and again that would be possible but it's quadratic times so if you have thousands of points that won't won't be efficient enough and with divide and conquer you can do it in in N log end time

12:27 um the the main idea is that you uh you divide if if those points lie in in such a rectangle you cut that in half and you recurse on the left and right side so you find you find the median in x coordinates so that half of the points are left and half are

12:55 right so I guess this is a bit misleading the line could not be doesn't need to be in the middle but half of the points are left half of the points are right how do you find the median ha we've just seen in the previous section right you can do that in linear time worst case even okay then you recurse on those two parts and then you you get back two pairs of closest points maybe two here and okay let's say the other two are here so you get to these two candidates and you can compute which one is closer to each other but you're not done because there could be points that are just around the dividing line so they're split by okay maybe a little bit more careful the the point is that the point is uh on either side of the line so these two might be closer but neither of the two half recursive calls would have seen the two the pair because they each got just one of them but the trick is that you can uh you know that you have this distance already so these points I mean they cannot look like that they cannot be so far away this would not be a a valid um a

14:13 viable candidate so instead you can find some range around this line and only the points in that range are potentially candidates for being closest um and you can further uh trim down how many of those there are um but I'll I'll stop here and just tell you you can you can look this up you don't need to know um I just wanted to show this as another example what dividing conquer can do um be beyond the simple uh sorting algorithms that's the key idea with enough time you can you can work out the version that has a a lock Square in the running time I