Angličtina pro matematiky II
COURSE MATERIALS WEEK VIII.
Listening Divide and Conquer
http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed03.htm
Decide whether the statements are true or false.
- The subject of the lesson is master theorem.
- Students should go to recitation on Friday.
- Homework should be submitted on Saturday.
- Monday is a holiday.
- Divide and Conquer is the same as divide and rule.
- The question of family feud will be on the quiz.
- Divide and conquer was practiced by the Americans.
- Cormen, Leiserson, Rivest and Stein are the authors of a book on algorithms.
- There are three steps in divide and conquer.
- The value of N is larger than it was in the original problem.
- Merge algorithm fits into this system.
- When you recursively solve each part of the array, it is divide.
Listen again and fill in the missing words.
Transcript - Lecture 3
Good morning everyone. Today we are going to do some algorithms, ___________ algorithms, and we are going to use a lot of the, well, some of the simpler mathematics that we developed last class like the master theorem for solving ___________. 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 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 _____________ for you to actually work on your problem set a few hours early.
Well, actually, it's _______ on Wednesday so you have lots of time. And there is no class on Monday. It is the holiday known as Student Holiday, so don't 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 ______ and tested way of conquering a land by dividing it into sections of some kind. It could be different political factions, different whatever. And then somehow making them no longer ______ each other. Like starting a family feud is always a good method. You should remember this on your quiz. I'm kidding.
And if you can separate this big power structure into little power structures such that you _________ each little power structure then you can conquer all of them individually, as long as you make sure they don't get back together. That is divide and conquer as practiced, say, by the British. But today we are going to do divide and conquer 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 _______ design. We're 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 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 don't really know how to solve it in an _________ way, so you are going to split it up into ___________. 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 smaller 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. You 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 ___________. And lots of algorithms fit it. You have already seen one algorithm that fits this paradigm, if you can remember. Merge sort, good. Wow, you are all awake. I'm ____________. So, we saw merge sort. And, if I am clever, I could fit it in this space. Sure. Let's be clever. A quick review on merge sort. Phrased in this 1, 2, 3 kind of method. The first step was to divide your ________ into two halves. This really doesn't mean anything 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 __________ time. And you say OK, I am pretending my array is now divided into the left part and the right part. And then the interesting part is that you recursively solve each one. That's the conquer. We recursively sort each subarray. And then the third step is to ___________ those solutions. And so here we really see what this means. We now have a sorted version of this array by induction. We have a sorted version of this array by induction
Transcript - Lecture 3
Good 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 mathematics 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 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, it's due on Wednesday so you have lots of time. And there is no class on Monday. It is the holiday known as Student Holiday, so don't 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 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. I'm kidding.
And if you can separate this big power 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 don't get back together. That is divide and conquer as practiced, say, by the British. But today we are going to do divide and conquer 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 design. We're 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 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 don't really know how to solve it in an 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 smaller 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. You 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, good. Wow, you are all awake. I'm impressed. So, we saw merge sort. And, if I am clever, I could fit it in this space. Sure. Let's 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 doesn't mean anything 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 now divided into the left part and the right part. And then the interesting part is that you recursively solve each one. That's 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 of this array by induction. We have a sorted version of this array by induction