Transcript3.docx

1、Transcript3Video Lectures - Lecture 3 Topics covered:Divide-and-Conquer: Strassen, Fibonacci, Polynomial MultiplicationTranscript - Lecture 3Good morning everyone. Today we are going to do some algorithms, back to algorithms, and we are going to use a lot of the, well, some of the simpler mathematic

2、s that we developed last class like the master theorem for solving recurrences. We are going to use this a lot. Because we are going to talk about recursive algorithms today. And so we will find their running time using the master theorem. This is just the same as it was last time, I hope, unless I

3、made a mistake. A couple of reminders. You should all go to recitation on Friday. That is required. If you want to, you can go to homework lab on Sunday. That may be a good excuse for you to actually work on your problem set a few hours early.Well, actually, its due on Wednesday so you have lots of

4、time. And there is no class on Monday. It is the holiday known as Student Holiday, so dont come. Today we are going to cover something called Divide and Conquer. Also known as divide and rule or divide et impera for those of you who know Latin, which is a tried and tested way of conquering a land by

5、 dividing it into sections of some kind. It could be different political factions, different whatever. And then somehow making them no longer like each other. Like starting a family feud is always a good method. You should remember this on your quiz. Im kidding.And if you can separate this big power

6、 structure into little power structures such that you dominate each little power structure then you can conquer all of them individually, as long as you make sure they dont get back together. That is divide and conquer as practiced, say, by the British. But today we are going to do divide and conque

7、r as practiced in Cormen, Leiserson, Rivest and Stein or every other algorithm textbook. This is a very basic and very powerful algorithm design technique. So, this is our first real algorithm design experience.We are still sort of mostly in the analysis mode, but we are going to do some actual desi

8、gn. Were going to cover maybe only three or four major design techniques. This is one of them, so it is really important. And it will lead to all sorts of recurrences, so we will get to use everything from last class and see why it is useful. As you might expect, the first step in divide-and-conquer

9、 is divide and the second step is conquer.But you may not have guessed that there are three steps. And I am leaving some blank space here, so you should, too. Divide-and-conquer is an algorithmic technique. You are given some big problem you want to solve, you dont really know how to solve it in an

10、efficient way, so you are going to split it up into subproblems. That is the divide. You are going to divide that problem, or more precisely the instance of that problem, the particular instance of that problem you have into subproblems. And those subproblems should be smaller in some sense. And sma

11、ller means normally that the value of N is smaller than it was in the original problem. So, you sort of made some progress. Now you have one, or more likely you have several subproblems you need to solve. Each of them is smaller. So, you recursively solve each subproblem.That is the conquer step. Yo

12、u conquer each subproblem recursively. And then somehow you combine those solutions into a solution for the whole problem. So, this is the general divide-and-conquer paradigm. And lots of algorithms fit it. You have already seen one algorithm that fits this paradigm, if you can remember. Merge sort,

13、 good. Wow, you are all awake. Im impressed. So, we saw merge sort. And, if I am clever, I could fit it in this space. Sure. Lets be clever. A quick review on merge sort. Phrased in this 1, 2, 3 kind of method. The first step was to divide your array into two halves. This really doesnt mean anything

14、 because you just sort of think, oh, I will pretend my array is divided into two halves.There is no work here. This is zero time. You just look at your array. Here is your array. I guess maybe you compute n/2 and take the floor. That takes constant time. And you say OK, I am pretending my array is n

15、ow divided into the left part and the right part. And then the interesting part is that you recursively solve each one. Thats the conquer. We recursively sort each subarray. And then the third step is to combine those solutions. And so here we really see what this means. We now have a sorted version

16、 of this array by induction. We have a sorted version of this array by induction.We now want the sorted version of the whole array. And we saw that was the merge problem, merging two sorted arrays. And that we saw how to do in linear time, order n time. I am not going to repeat that, but the point i

17、s it falls into that framework. I want to write the running time and merge sort as a recurrence. You have already seen the recurrence, you have already been told the solution, but now we actually know how to solve it. And, furthermore, every algorithm that follows the divide-and-conquer paradigm wil

18、l have a recurrence of pretty much the same form, very much like our good friend the master method. Lets do it for merge sort where we sort of already know the answer and get a bit of practice.This is the merge sort recurrence. You should know and love this recurrence because it comes up all over th

19、e place. It comes from this general approach by just seeing what are the sizes of the subproblems you are solving and how many there are and how much extra work you are doing. You have here the size of the subproblems. It happens here that both subproblems have the same size roughly. There is this s

20、loppiness that we have, which really should be T of floor of n over 2 plus T of ceiling of n over 2.And when you go to recitation on Friday you will see why that is OK, the floors and ceilings dont matter. There is a theorem you can prove that thats happy. You can assume that N is a power of 2, but

21、we are just going to assume that for now. We just have two problems with size n over 2. This 2 is the number of subproblems. And this order n is all the extra work we are doing. Now, what is the extra work potentially? Well, the conquering is always just recursion. There is sort of no work there exc

22、ept this lead part. The dividing in this case is trivial, but in general it might involve some work. And the combining here involves linear work. So, this is the divide-and-conquer running times.So, this is the nonrecursive work. And that is generally how you convert a divide-and-conquer algorithm i

23、nto a recurrence. Its really easy and you usually get to apply the master method. Here we are in Case 2. Very good. This is Case 2. And k is zero here. And so in the recursion tree, all of the costs are roughly the same. They are all n to the log base b of a. Here n to the log base 2 of 2 is just n.

24、 So these are equal. We get an extra log factor because of the number of levels in the recursion tree. Remember the intuition behind the master method. This is n log n, and that is good. Merge sort is a fast sorting algorithm n log n. Insertion sort was n squared. In some sense, n log n is the best

25、you can do. We will cover that in two lectures from now, but just foreshadowing.Today we are going to do different divide-and-conquer algorithms. Sorting is one problem. There are all sorts of problems we might want to solve. It turns out a lot of them you can apply divide-and-conquer to. Not every

26、problem. Like how to wake up in the morning, its not so easy to solve a divide-and-conquer, although maybe thats a good problem set problem. The next divide-and-conquer algorithm we are going to look at is even simpler than sorting, even simpler than merge sort, but it drives home the point of when

27、you have only one subproblem. How many people have seen binary search before? Anyone hasnt? One, OK. I will go very quickly then. You have some element X. You want to find X in a sorted array.How many people had not seen it before they saw it in recitation? No one, OK. Good. You have seen it in anot

28、her class, probably 6.001 or something. Very good. You took the prerequisites. OK. I just want to phrase it as a divide-and-conquer because you dont normally see it that way. The divide step is you compare X with the middle element in your array. Then the conquer step. Here is your array. Here is th

29、e middle element.You compare X with this thing if lets say X is smaller than the middle element in your array. You know that X is in the left half because it is sorted, a nice loop invariant there, whatever, but we are just going to think of that as recursively I am going to solve the problem of fin

30、ding X in this subarray. We recurse in one subarray, unlike merge sort where we had two recursions. And then the combined step we dont do anything. I mean if you find X in here then youve found X in the whole array. There is nothing to bring it back up really. So, this is just phrasing binary search

31、 in the divide-and-conquer paradigm. It is kind of a trivial example, but there are lots of circumstances where you only need to recurse in one side.And it is important to see how much of a difference making one recursion versus making two recursions can be. This is the recurrence for binary search.

32、 We start with a problem size n. We reduce it to 1. There is an implicit 1 factor here. One subproblem of size n over 2 roughly. Again, floors and ceilings dont matter. Plus a constant which is to compare X with the middle element, so it is actually like one comparison.This has a solution, log n. An

33、d you all know the running time of binary search, but here it is at solving the recurrence. I mean, there are a couple of differences here. We dont have the additive order n term. If we did, it would be linear, the running the time. Still better than n log n. So, we are getting rid of the 2, bringing it down to a 1, taking the n an