Video 2-8: Algorithm Design Teaser

0:03 Now, of course, here is the point where algorithm design really shines. We're not stuck at this quadratic running time for the maximum subarray problem. We can do way better. And I'll show you also at the end a bit what this means in in actual time. Um, how could you possibly do better in this problem? you somehow need a way to exclude many other ranges from further uh consideration by um proving implicitly that they cannot be better than what you've looked at so far. Some of these um solutions will come a bit out of nowhere and they will appear a bit magical. That's on purpose in a way. Uh you'll see the more systematic way to get there in follow-up units. For now, it's rather a bit of a flashy example where these techniques work really well and produce really cool results. Uh, one idea one might have is this slightly crazy one. Uh, if I have this this range in my array from 0 to n, maybe there's something special about the middle point. And either way, um, I can classify the optimal solution.

1:12 there's some final some final um range J that will deliver the optimal subset sum subrange sum and it is one of these three types. It either lies entirely to the left of the middle point, then we call it type A solution, or it's entirely to the right of the middle point, that's a type B solution, or neither of the two. But that means it straddles the middle points. The starting point is to the left of the middle and the end point is to the right of the middle. One of those three will certainly happen. Now maybe this is not clear why this would help but you'll see um that this allows a certain design technique for algorithms to bite namely a divide and conquer that will come come to for a few a full unit later. The idea is that these middle these point C solutions are a bit easier than the others because that's now a property of the subset sum problem. If I fix that I want to how somehow contain this middle point, I can independently pick the best starting point and the best ending point and they don't influence each other. If there's some optimal solution that contains the midpoint, it has to have the optimal range from the start until the middle and then the optimal part from the middle until the end. If there was any other combination, I could always swap out the prefix or suffix and make the solution better. So I cannot have that and that means my quadratic problem of trying all start and end points all combinations or the point C problems the point C solutions reduces to something where I do f first the start point then the end point so that's n plus n maybe or n half plus n half not the multiplication question.

3:22 Uh don't worry, you can round this in some way. If if you look to the left, it actually is rounded. Uh this is just for the picture. There's nothing magical about this middle point. I could have picked n over three. You round it down. There's up to this point nothing magic about the middle. You can do this with any specific point. There's always going to be three types of solutions. either to the left of this middle of this magic point or entirely right or they contain it and those that do contain it are easier because I can independently optimize. That's the insight here. And as the slide already gives away for A and B, we kind of just apply the same procedure again, but now using the fact that I know I'm restricted to a smaller range. Now this will not solve the problem yet. In this left half, I will again have a range. So I'm considering the middle here again. And I'll keep doing this recursively.

4:19 But because I'm cutting the length of the array in half, and that is now where the middle is useful, a third would have also worked in a way up to constant factors. Uh but half is giving you the best balance of getting rid of many elements on both sides.

4:37 Again, um I'm going to go through this in a bit too much pace for you to follow entirely. We'll come back to divide and conquer either way. Uh but you can puzzle together a solution. Tada. Here's the code. Um that that follows this recipe. It's a recursive solution that tries to find the maximum subarray only in a restricted range only from L to R. If that range is empty, then uh clearly we can't do anything better than picking no elements. If it's a single element, I have the two options of not picking anything or picking that single element. Uh for any larger ranges, I can define something like a middle point and it is rounded. So it it may not mean exactly equal halves but roughly. Then I'm going to find recursively by just calling the same procedure on these first and second part of the array. I'm going to find all solution or well I found find the optimal solution of type A and type B respectively.

5:40 And by that I've reduced the problem to checking if the optimal A solution or the optimal B solution or any of the C solutions are better. And so the rest of the code does just that. uh it finds the best left point, left end point, the starting point of of our um middle type C subarray. So starting point is is this SL uh and you just check um what gives you the maximal sum and you do it from uh from the midpoint to the left so that um you can reuse your computed subsums again and you do the same on the right or from the midpoint to the right. So after that uh the solute the best solution of type C is the sum of whatever the sum in the prefix and the sum in the suffix gives you. So the picture for this um would be like this. Here's our middle point. Then I scanned leftwards until I found I mean I'm scanning all the way but I remember where was the best uh starting point for this. Then I get here the sum SL. Here I get the sum SR.

6:55 So for the types uh the type C endpoints the type C ranges sorry the best is to sum up these two individual parts and then the final solution is just the best of the three options that we have. Why does this work? Why is this correct? Formally, it's an inductive proof, but as a a vague intuitive argument, you should just make sure that these three cases are mutually exclusive. You'll always have an optimal solution that's either A or B or C, and then nothing else is possible. And for a recursive procedure, the natural thing is to prove inductively that it correctly computes the maximum subarray sum. And this follows the code structure. So I think it's it's worth going through this once and you'll practice more in the tutorials on other examples. Uh we do an induction over the length or the number of elements in the range that we call this function on. If it's at most one element then we have these two special cases and those clearly do the right thing. There's not much uh that you can do incorrectly.

8:09 Then assuming that this function gives the right sum of the maximum subarray up to n minus one elements. I'm now making the inductive step. I'm assuming here that I have at least two elements otherwise I would be in the basis in the base case. And then uh I have some optimal solution somewhere. I don't know where it is but it will be either type A or type B or type C because there's no other options. If it is one of type A or type B, the inductive hypothesis tells me the recursive call on that subarray will find precisely this sum. And then I'm going to return it because it's larger than the other options. And part C would need a slightly more careful analysis if you want to do it very formally. You've seen last time uh how you you do these loop invariance and that's what you would want to do here and you do it twice for the two left and right sides. But maybe the code is easy enough that you would believe me that this works by essentially walking over all possible options and remembering the best that gives us the correctness of this uh recursive algorithm. Now, what is maybe least obvious is how fast is this?

9:31 Because hopefully we get rid of a lot of different uh cases here, but we this recursion somehow feels a bit like cheating. We don't really seem to get away from checking all possible options at the end of the day. Uh if um one of A, B, and C is always true and we have to find the best possible among the A's and the B's. Still the trick is we do get something and the formal way to do this will also look again in more detail but let me go through it uh from bird's eye perspective. We'll try to also put the analysis in recursive terms. This is a recursive function. So its cost will be a recurrence relation. Uh the first tutorial sheet if you looked at it already due on Friday um has some of these as well and you'll um practice one at the in-class sheets. Uh so after that at least this should make sense.

10:32 Uh first let's analyze the nonrecursive part. So anything that happens below here. Um here I'm doing mus l and r minus m additions in these two loops.

10:52 and then the one down here that gives me a fixed cost of n + one or the part that I'm doing without calling the function recursively. This part I definitely have to pay if I start with uh a list that doesn't have one or two zero or one elements only. So in in general let's write capital C of N for the total cost that I get when I call this function on an on an array of n elements. This will be clearly the cost I pay at the end for the non-recursive part. But I have to take into account that I'm calling myself recursively. So I have this cost of the first recursive call and of the second. And there the rounding you have to work out uh which way it goes. Um to make our life a bit easier, we're assuming here that the input size is a power of two. Um for just a a rough upper bound, you can always say I'm I'm going to append to my array some zeros to make it a power of two long for the sake of the analysis. That will only make the algorithm slower and doesn't really affect the result. uh but then I can make the recurrence a bit easier because if n is a power of two there's no rounding happening it always nicely evenly divides and then these two terms are the same right they're both n half so if I rewrite this so that it's a function in k uh I make out of uh 2 to the k I get to the k minus one and I get this twice that's why I have this factor two here I have two identical in terms of the costs to identical recursive calls. [snorts] Now, how to solve these kinds of recurrences? If you arrive at this point, you may try to just insert and guess and that's not a bad idea in general and [snorts] then um you can work it out. We'll revisit this um in more detail uh in upcoming sections. So maybe for now for the sake of of making progress, let me just throw the solution at you. You can even show here that with tilda asmtoics uh you get a precise um statement for for that simple case turns out even true in general. Um if you seen master theorem then hopefully this will sound familiar. That's precisely one of the recurrences after the simplification with powers of two. Um it's d it's exactly the form that you can solve with the master's theorem.

13:27 So let me um not sweep under the rack though uh how powerful this was because we got from gravic to n login and that is a a very sizable difference to make you um appreciate this a bit more.

13:50 Let's um see some running times for this. So here's a a little visualization that has all these uh different algorithms built in. And let's start with this brute force method and run it on a bunch of inputs between one and 300 elements. And then we'll get um a plot where we have on the x-axis the input size and on the y- axis well on the right hand side it's the time in milliseconds. It's still rather fast because it's only 300 elements. And on the left hand side we have the number of additions. So the the precise thing that we counted with the recurrence well for the um divide and concrete. This was the cubic algorithm. That's what we started with where uh we recmp compute all the sums. If we do the same with the quadratic version where at least the sums were reused, this already is way smaller. If you look at this here and so maybe let's just have the yellow one. You can see the running times here are almost uh so fast that it's a bit hard to measure. So we might have to uh increase this upper bound a little bit to see more.

15:12 And this third algorithm that we've seen now this n login algorithm that's the divide and conquer we we just looked at is even compared to that again way faster and we can add this one again but now it completely drowns the others. The only choice you have is to do a log log plot. Then you can still fit all of them on one picture. This may be informative in keeping them all in in comparison. It's a bit problematic for the interpretation because the difference here doesn't sound doesn't look so dramatic, but it's really stark. And if you switch back here, you see why, right?

16:06 let's maybe do this first. Uh there's also a little race for these different methods and let's go a bit nuts. So 8,000 elements. What you see here is for each of the 8,000 elements, it tries it tries to draw a line, but it's already not enough pixels there. If you start this for the brute force method, it'll take a while and I can even add the uh quadratic one and it just catches up while this is still running and the dividing conquer is even faster. You see here this this bar is on a log scale. So this was 100 milliseconds and this was 10 on even 8,000 elements. Okay, this will eventually finish. uh the cubic algorithm is clearly useless and that's for 8,000 elements. Okay. Now with this problem we're not yet done as you may have seen if you were uh careful uh carefully watching the animation. From a practical perspective you could say this is good enough. This nlo algorithm is essentially scalable. When you double the input you just need twice as long. So you could say uh if you make the machine twice as big and the input is twice as big you're almost fine.

17:23 So um at that point you could stop um and be happy. Now there's two more things that algorithms people like to do. Number one is can I potentially prove that this is the best possible algorithm in which case I can definitely stop if I'm provably best.

17:44 Now what we can prove here is that something slightly weaker is true. Any algorithm that correctly finds the maximum subarray uh sum needs to have linear time. And the algorithm the argument is extremely simple. But let me walk you through it also to point out how useful it is to have these impossibility results because it means you can instantly stop trying to find a solution that's faster than this. And uh because the argument is so easy um you can also convince anyone about this fact. So how would you prove this? Uh for this for this lower bounds all that we need is an adversary argument. So um we assume um we have some correct algorithm a that somehow um finishes without reading all the cells. And note that what is the converse of needing omega of n time? So we would assume here that a has running time little o of n. If it's not omega n is there's stuff in between. Let's say let's say you want to disprove that it can be much faster than this then certainly it doesn't have time because that already takes linear time.

19:16 So the proof makes this slight shortcut. It actually proves a slightly different statement. It's it says no algorithm can get away with not looking at all the numbers and that uh implies it needs linear time. So suppose an algorithm somehow computes correctly the subarray sum without looking at all uh the input cells. So in particular it hasn't read cell I. [snorts] The algorithm will put some claim as its output. This S is the sum of the largest subarray. Okay.

19:53 Now there's uh there's two options. Um either way uh either this this range contains my that's a bit bad that it's the same notation. Let's call this I star the one that it doesn't read.

20:14 Uh either this range contains IR or it doesn't. But the same modification to the input um puts um shows that the algorithm makes a mistake. If I'm putting into this this position that the algorithm has not read a number that's bigger than the sum that the algorithm claims, then clearly what the uh algorithm output would be the same on this modified array because it hasn't even looked at my changed cell. Okay, so I would output the same S again, but clearly this is wrong because I can pick this one element range and that has a larger sum than S by definition. And so A cannot be correct on this modified array, but it also doesn't distinguish the two. So the adversary argument here comes from this idea that uh some uh some malicious person is trying to just modify the input while you're working on it. And as long as the algorithm doesn't make sure that it gets to know which choice the adversary made, it might still fool it. And in this case it's very easy. I can fool the algorithm uh by just making a very large number precisely in the spot where the algorithm says where the algorithm didn't didn't look. Okay, [snorts] so that was a contra a proof by contradiction. We've assumed there is an algorithm that doesn't need to look at all cells and we've proven that such an algorithm cannot be correct. So there is no correct algorithm that doesn't look at all cells and hence any algorithm needs linear time.

21:54 Okay, so we've made some progress. We have a lower bound of omega n time for solving this problem and we have an upper bound of big o of n login. We have an algorithm that achieves to find the maximum subarray in n login time. Now again you could say fine this is close enough. I'm going to go home for this problem. You can close the gap and the truth is that you can improve the algorithm. And the truth is that you can even improve it by an a very embarrassing simple algorithm that once you've seen it um I think you won't forget again. But I I don't know if it's easy to come up with if you haven't seen it before.

22:41 It's a very simple sweep line algorithm. It does essentially just two things. Uh you do one run from left to right across your array. Now suppose you have processed this prefix of the array already. You maintain two things. You maintain the the best S you've seen so far anywhere in this prefix and you maintain the best S you have seen so far that ends precisely at your current position.

23:21 And then if you go if you go to the next position there's first of all for the green thing something has to change. I can either add this new number then I'm extending the green range and the start here stays the same. If that is better the only other option is to essentially start at zero. Again, if this is a um a really large negative a really small negative number, it might mean that just picking the empty range here is better than picking this number. And I'm forced to end right here. That's the restriction of the the suffix max. And you can think about no other option exist. If um if there was some other optimal solution, hypothetically the best from here to here would be this. Then also on the array with one shorter, this shorter range would be better than the green thing. So that contradicts the choice you had up to this point.

24:23 If you correctly maintain that this suffix max is indeed the largest sum that ends at your current position, then the only two options you have to check are precisely these here. Either you extend it by adding the next number or you start at zero. And then for the global max, there's again two options. Either the previous one stays the best or this one single thing that you now found is better. And if so, you take it.

25:00 Now, of course, um it's not hard to believe that this algorithm is even faster than the others. Let's uh just compare the other the last two.

25:14 Boom. And um let's restart the race maybe. Ah, you can't see. Sorry. Here's again the the two plots you've seen before. Um let me run it again maybe. So the n login algorithm was this bit scattered for these small inputs and the linear is just uh hardly measurable. Um and for this race let me not include the brute force one because it won't ever finish before I lose patience. Maybe we can make the input a bit bigger. 120k and uh still you see this linear algorithm six milliseconds. I think that's at the boundary of what you can sensibly measure. And even the quadratic one now doesn't really finish. And if you go to a million elements, you start to see the difference between n login and linear 280 versus 90 and 4 million 1 second versus 40 milliseconds. So in this case there's of course two things happening. It's a different order of growth but also the divide and conquer has extra overhead for the recursion etc. So this it's both um the asmtoic growth and the constant factor in front that uh favor this linear sweep s simple linear time algorithm.

26:49 In that sense this problem is a bit exceptional in that there is such a simple optimal solution that you can write in in six lines of code. That's not usually the case. uh but the fact that you can go from something cubic quadratic to n login is rather common in the problems we'll look at and is always worthwhile from a practical perspective.

27:15 Okay. Um if you want to formally prove the correctness you can do this again by um an induction over the loops or an an invariant over the loops and you just prove that these two things do what the name suggests. That's what I've tried to informally argue on uh my picture. And the running time is kind of not worth mentioning. You do exactly the addition here and you do that once per iteration. You have any iterations done.

27:48 If it only always was that easy.