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

0:02 now in this second part I just want to tease her a few things without explaining them in detail so I I don't expect you to follow this um to the degree of detail that we've done the other algorithms of this in this unit that's my compromise I was I was asked to show you a few other dividing conquer examples but I felt we won't have enough time for the other things so the compromises show you the key ideas uh skip the details you're not expected to know the details obviously if I haven't shown you the first problem I want to look at is called the majority problem that's again very fundamental question you have an array of of things this time I'm not even assuming that they're ordered in some way it could be arbitrary objects as long as you can take two objects and tell me if they're the same I'm happy and the ask the question is is there an object in this array that occurs in more than half of the positions a majority in the in the straight sets okay so it could be some same election right it's uh spelled for some some leader of some country without a prime minister or something but uh not that we're having any elections right just a few people

1:19 deciding but uh let's stay with the abstract problem it's not so clear uh if you can't use sorting how to do it you could just take um this set it is a data structure they are just like can't decide what they said and see if it's like because I don't feel like this is said so yeah just reduce the middle communicates and then interpret decide on girlfriend without kisses yeah

2:09 I don't hate the approach uh let me comment on the very naive solution first then I recap Your solution which uh is is interesting but I don't think it's the the is the most efficient way so the if you know nothing about the elements you could just take every pair and compare them and see so you could you could take any of the elements in the array and guess yeah that's that's probably my majority so I'll just compare all the others and check how many are equal if I find anyone that has more than n half votes I'm I'm happy I found it and otherwise I take the next element and keep going if you do this for all the elements the worst case is quadratic right that's that's definitely doable but very slow

2:54 um your suggestion was you could at least in Python this is a single line you could take the array or list of elements and turn it into a set so that's uh it's a different data structure I mean python under the hood uses some hashing it could be a binary search tree uh so this is a way to get rid of all duplicates so you get a second list second set that does not contain any duplicates um I'm not sure how how you get very quickly from this to if if the set has too many elements You can conclude there is no majority that direction works the other direction say if the set comes back with uh with um square root different elements and the original array had n it's not clear how you find which of these square root elements is a majority there probably is one or maybe not maybe they're all equal so it's not so clear um

3:55 it's in the section on divide and conquer so probably the the idea is to somehow throw divide and conquer at this and see what happens so let's do that uh

4:08 and let's do the simplest version of dividing concrete we just cut the array of elements into two halves equal size now if the overall array has a majority element this also must be a majority element in either the left half or in the right half or actually in both right this is uh you can easily show this by contradiction if it wasn't the majority not in both halves then there's not enough uh occurrences for the entire array so we could try to do some some recursive uh procedure that tries to find the majority recursively in the left half and in the right half what it comes back with is at most two candidates one left and one right one we take these two and compare everything with those and check if they are majorities if one of them is happy and you return if both of them are none which could happen they're just majorities in their halves but not overall then your return there is none

5:09 uh if you if you implement this you get something like the merge sort cost because you have a similar recurrence you have two calls for roughly half Buddha um no I'm not sure how you mean

5:39 oh okay of this algorithm um I didn't put code on the slides um so you need some some boundary condition when to stop is a recursive algorithm so if you have a single element you just return that element it's a majority of the one element array otherwise uh you split in half now

6:04 um there's the uh annoying Corner case if you have an odd sized array uh you might you might want to split it into n half rounded down in half round it down and keep the one element separate and do a special case check for that element whether that's a majority yes or no

6:28 um I think if you just cut things in half uh it's it's at least more tricky to argue that it's correct this will not be the final solution I have a better algorithm for you in the next slide that's why I decided ah does not bother with the code I I want to briefly mention why the um the runtime would be n log n again okay so this is this is only roughly true

6:58 um yeah I'm I'm running a little short on time I noticed so let's keep this short you would you would need linear time to check the two candidates and you recourse two times that's virtually the same recurrence as for merge sort so the solution is also similar

7:23 a better way to do it is actually not really use dividing concrete sometimes so that's my my other message sometimes it's good to not look too narrowly there's a really Nifty algorithm that is called majority in this weird spelling um don't blame me it's the inventor's choice so you go through the array once you keep an element at the beginning it's just the first one and my next element arrives this is the current Contender to be the majority if a new element arrives and it's the same you increment the counter for this element if you find a different element you decrement the counter and if the counter reaches zero you switch to the new one and you just keep going like this you will end up with a single element at the end and now the amazing thing is if the array has a majority then this element is it if the array does not have an not have a majority this element will be arbitrary so you still need another check the element yet that you get returned you need to check again how often does it occur but the algorithm is very simple it's obvious that it's in linear time because it just runs through the array once and a second time to check

8:37 and the the correctness arguments uh is basically you you play duels is imagine there's there's a a drug gang war and uh the question is is there is there a gang that survives by having the majority of the fighters whenever element whenever someone stands up and a new element arrives either it's from the same gang they join up or it's another one and they both get shot and so there's one less less remaining so if there's a majority that majority gang will at the end survive otherwise it's some random gang uh I'll I'll leave it with that uh for this one I want to mention one last problem without giving you at all any detail about how to solve it but I want you to know that this solvable this way because it's uh it's a Nifty problem and it seems even less clear that you can do it you're given points in the plane so 2D points they have an X and a y coordinate uh and of such points and your task is to find the two points that are closest in the standard euclidean distance

9:54 you can again do this naively by taking every pair of points Computing their distance and then keep the ones that had the minimum distance but with a lot of more work you can do this in N log n time again with some dividing conquer ideas the gist of it is you can sort the points by x-coordinate and then split in half the left points and the right points find the closest pair recursively in in the two sides and then the closest are either in the left half or in the right half or it's points that straddle the dividing line one left one right and so for this last step you can exploit that those two points can't be too close there cannot be too many points close to the dividing line because you found the minimum distance on the left and on the right so these can't be closer and that way you can limit the time you need to check all these these points in the middle the details are a bit messy and tricky and there's several steps before you get to the final time so uh it's not it's not obvious to spell out the the version in N log n time you probably first want to think about a version with n log squared and time

11:08 uh I decided to skip the details just in the interest of time I just wanted to show this as as one example where dividing conquer gets you a long way from from N squared and all all simple ideas lead to N squared in this problem but you can do much smarter things uh with a clever dividing conqueror