0:03

Next to finish off our study of recurrence relations,

Â we'll talk about the master theorem for divide and conquer recurrences.

Â This is very important in the theory of algorithms.

Â It's all about divide and conquer algorithms.

Â So many algorithms gain their efficiency by attacking a problem of size and

Â with the following steps.

Â 0:25

First divide it into smaller parts, so

Â in the case of mergesword it was divided into two parts of size n over 2.

Â More generally it might be parts of maybe different size.

Â So we'll pick effect or beta, so it could be n over 3 or n over 4, whatever.

Â And not only that, it might not add up to n.

Â So there might be multiple parts, and say three parts of size n over 2 or

Â 7 parts of size n over 8.

Â Or whatever, so we'll parameterize both the number of parts and

Â the size of each part.

Â Usually, they try to do equal size.

Â If you don't have equal size, then you have even more complications.

Â So that's the first thing, divide into alpha parts of size n over beta.

Â And then solve recursively, and then put the solution together somehow with

Â extra cost that is described by a standard function.

Â And in the theory of algorithms, remember we don't care about the constant,

Â we just want to get the order of growth.

Â So we'll say theta of n to the gamma, log n to the delta.

Â So there's a lot of problems that fall within this paradigm.

Â And again, it's easy to write computer programs that have this kind of behavior.

Â Just write a recursive program that does the things.

Â And so for the theory of algorithms for decades, people have been developing

Â computer programs that gain their efficiency by this strategy.

Â And what we want is to analyze them.

Â So very early on,

Â people started studying general models for computer programs like this.

Â And that's what's called the master theorem that we'll talk about next.

Â So first, here's some examples.

Â So we did merge sort.

Â For merge sort, problem sizes N/2, so that's beta 2.

Â Two problems in size N/2, so that's alpha is 2.

Â And the extra cost is N, so there's no log n.

Â So delta equals 0, gamma equals 1.

Â So that's .mergesort.

Â 2:40

Here's another example that's similar.

Â So that's Batcher's network for sorting, so that's a different

Â approach to sorting where we don't do it with programs but we do it with hardware.

Â And batchers is like mergesort, except the extra cost has a login factor.

Â So this delta equals 1.

Â That's Batcher's network.

Â So now I'm going to only write the ones that are valid when n is the power of 2.

Â Taking into account the floors and ceilings that are needed for

Â general n takes us to another level that we

Â don't necessarily need to worry about in many cases with the theory of algorithms.

Â And so we'll try not to worry about that in this first cut at the analysis.

Â A famous algorithm that got people interested in this, was multiplication.

Â At the beginning, people were wondering how

Â 3:38

difficult is the problem of multiplying two n-bit integers.

Â And it seemed like the best you could do would be the grade school method of

Â multiplying two n-bit integers by taking each bit, multiplying by the all

Â the other bits, moving over one, and then adding up the little n-by-n table of bits.

Â That's going to take time proportional to n squared.

Â And then the Karatsuba multiplication algorithm came along,

Â where they showed how to multiply input integers,

Â by dividing into three problems, of size n over 2.

Â And then combining with an extra cost of n, and so that's the number

Â of steps required for that particular multiplication algorithm.

Â And a related one that's also very famous is the Strassen matrix multiplication,

Â however though.

Â Seeing the matrix multiplication algorithm, where you have two

Â N by N matrices that you want to multiply together to get the N by N result.

Â Seeing that, for every entry in the result,

Â you needed to have a dot product of a row and a column.

Â Which is going to require n multiplications for

Â each of the n squared entries in the result, which would be n cubed.

Â But Strassen showed that you could solve it with a divide and

Â conquer algorithm where you divide into seven problems of size N/2,

Â and then get the final solution with an extra N.

Â So it was an algorithm that did matrix multiplication in a number of operations

Â described by this recurrence.

Â So these are three examples of divide and

Â conquer algorithms that all have the same general character.

Â And so with the master theorem, it says that it gives a,

Â under the supposition that you have

Â a problem besides alpha parts of size n over beta with extra cross omicron

Â n to the gamma log n to the delta that's going to lead to a reoccurrence.

Â 5:49

And the reoccurrence is going to look a lot like our merge sort reoccurrence,

Â except instead of the floors and ceilings, we add little tiny

Â constants to each one of the problem part sizes.

Â N over beta when it has to be an integer, so you have to have some floors and

Â ceilings in there somewhere or maybe the problem size is to throw out a few terms.

Â So, as general as we can do is to get alpha terms of the form N over beta

Â plus O of 1 and then we add on the extra cost and

Â the master theorem gives the order of growth of the solution.

Â And it all has to do with the relationship between this

Â extra power gamma in the extra cross term and

Â the log to the base beta of alpha or alpha's the number of parts and

Â beta is the amount, the fraction that you divide n by.

Â 6:52

So and what the solution is, is three different cases.

Â If gamma is small compared to log beta of alpha,

Â it's n to the gamma log n to the delta.

Â If it's equal, then there's an extra factor of log n, and then if gamma is big,

Â so that means the extra cost is big, then that's going to dominate n.

Â And it's n to that power.

Â And so here's in the book is a little graphic way seeing

Â how these three cases have to be different.

Â So this is the case that alpha equals 3.

Â So we have three parts and so it has to do with

Â the relationship our number of parts and the size of each part.

Â And the one in the middle is like what we did with mergesort.

Â If you have three parts of size N over 3, then the total number of problems that you

Â analyze in every case, the size of them is going to add up to N at every stage.

Â It's just that you divide by 3 every time.

Â And then every time you divide by beta you keep going until you get to 1,

Â so that is the log beta of n, this should say n, not alpha.

Â And so that gets you down to a problem size of with log and

Â steps you get down to problem size of 1.

Â So that's where you get the extra log n factor.

Â 8:27

If, on the other hand, you're dividing into,

Â so three parts, but they're small, then what's going to happen

Â is that really all that matters is the first cost.

Â And the rest of them become not so significant.

Â So really the cost of doing it the first time is what counts.

Â But if your problem sizes are bigger,

Â then it's all about the number of problems that you get at the end.

Â And that's what N to the log beta of alpha comes up.

Â So that's the master theorem for divide and conquer algorithms.

Â So here's the typical applications.

Â So, This is for mergesort,

Â you get N log N, for Batcher's network you get the extra factor of log N.

Â For Karatsuba multiplication you get best case here,

Â so it's N to the log base 2 of 3 which is about

Â 1.585 not N squared, it's less than N squared.

Â And for Strassen you get N to the 2.8, it's less than N cubed.

Â So the basic idea of the Master Theorem is that it give us good

Â asymptotic growth rates.

Â And very important for the theory of algorithms to help us understand

Â 10:02

Now, there's a lot of versions that have been studied about the Master Theorem.

Â There's some cases where you can get precise results like we did for

Â mergesort, and for the most important algorithms that people use in practice,

Â and we want to predict performance and compare algorithms, we have no choice but

Â to go there.

Â The more general results in the theory of algorithms,

Â you can go even more general than where we went in terms of

Â the extra cost of doing the combination.

Â And those are certainly available.

Â And then actually very recently, a full solution using

Â analytic combinatorics was developed by Szpankowski and

Â Drmota that actually captures in general,

Â all the kinds of oscillations as we determine for mergesort.

Â Now really appreciating how and why the solution works in the way

Â that it does is going to be something that's going to require everything

Â that we cover in analytic combinatorics, including part two.

Â But people will have some idea for how the mathematics manages

Â to model what actually happens in the computer algorithm, and

Â this is really an important contribution of analytic combinatorics in this case.

Â 11:36

So that's the Master theorem for studying divide and conquer algorithms.

Â And that'll complete our study of recurrence relations.

Â Next time we'll move on to generative functions.

Â So here are a few exercises that would be worthwhile for you to take a look at to

Â cement your understanding of this material in order to be ready for the next lecture.

Â 12:00

First one is Exercise 2.17.

Â There's a particular data structure called a 2-3 tree.

Â That doesn't matter too much now what it is but

Â there was a paper by Yao that proved that a certain property,

Â of this tree, which is described here,

Â is described by this second order, first order recurrence.

Â And so, it's a complicated first order recurrence.

Â And so, problem is to go ahead and solve this recurrence.

Â And it's an interesting random process.

Â And leads to interesting occurrence that's got

Â a solution that's definitely a practical interest.

Â [COUGH] Here's another one is to go ahead and

Â try divide by three and conquer.

Â So a sub n equals 3, A over 3 plus n.

Â So maybe mergesort by dividing into three parts and then doing a three way merge.

Â 13:23

the interesting performance behavior of something like this and

Â think about how we might compare two algorithms like that.

Â Now, in order to address those, you're going to, again,

Â want to read the chapter on recurrences in the book and

Â write up the solution to the 2-3 trees exercise.

Â And set up standard draw or

Â come up with your own way to plot the values of sequences.

Â And then go ahead and do that exercise for plotting.

Â Divide by three and conquer.

Â I think doing that work will help you make sure that you understand

Â the material that we've done so far and set you up for the next lecture.

Â