Solving Recurrences

Loading...

En provenance du cours de Princeton University

Analysis of Algorithms

41 notes

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Princeton University

Analysis of Algorithms

41 notes

This course teaches a calculus that enables precise quantitative predictions of large combinatorial structures. In addition, this course covers generating functions and real asymptotics and then introduces the symbolic method in the context of applications in the analysis of algorithms and basic structures such as permutations, trees, strings, words, and mappings. All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

Generating Functions

Since the 17th century, scientists have been using generating functions to solve recurrences, so we continue with an overview of generating functions, emphasizing their utility in solving problems like counting the number of binary trees with N nodes.

Ordinary Generating Functions16:25

Counting with Generating Functions27:31

Catalan Numbers14:04

Solving Recurrences18:55

Exponential Generating Functions7:23

Rencontrer les enseignants

Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

Now we're going to take a look at the use of generating functions to address the

important tasks that we brought up in the last lecture.

programs many of which can be casts as recursive programs or algorithms

immediately lead to mathematical models of their behavior called recurrence

relations and so we need to be able to solve recurrence relations in order to be

able to analyze algorithms. And so now, I'll take a look at how you

use generating functions to solve recurrence relations.

and it's pretty much a algorithmic process that is we want to we want hate

to use a meat grinder, but it gives the idea.

We want to put in a recurrence relation and we want to turn the crank and we

want to get out a sequence. We want to get out of a simple expression

for what it represents. and it's pretty much a general procedure

that we can always follow. I'll give many examples.

So first thing is we're going to make the recurrence valid for all values of N and

the, it's easy to do that and I'll show you in many, in the examples.

Then, multiply both sides of the recurrence by z to the n and sum on n.

so it's an equation that's valid for all n so that we can do that.

And usually, we make it just for nonnegative n.

then that'll give us some sums but some of those sums will involve the, an, an

unknown generating function and maybe some well-known generating functions.

the end result will be an equation that's the OGF corresponding the recurrence has

to satisfy. so then, what we need to do is to solve

that equation to get an explicit formula for the OGF.

a lot of times we can go ahead and do that and we'll get plenty of examples.

the initial conditions play a role. and then we'll expand the OGF to find the

coefficients. So, the recurrence corresponds to a

sequence. the OGF is a way to represent the

sequence. We'll use the refer, recurrence to find

out what the OGF is and then we'll expand to get the coefficients which is the

goal. That's, that's what we're trying to find.

so let's look at the example. Now, in the case of linear recurrences

with constant coefficients the procedure really is an algorithm.

We always can get a solution and actually people have implemented this in symbolic

mass systems. So so here's an example from the previous

lecture. so that's a recurrence that is defined

for n bigger than 2 with the initial conditions a 0 to 0 and a1 = 1.

so the first thing is make it valid for all n and so it's all n greater equal to

0. And so, all we do is use a kronecker

delta notation. so for one this thing and you assume that

for negative indices of 0. so a0 = 0 so that would be 0, that'd be

0. So for a1, we'd have to add a1, so, when

n is 1 we want to add 1. That's what that kronecker delta is at,

the right there. A0 is expressed then in terms of a's with

negative indices which is 0, so its okay a0 = 0.

So that's how recurrence is valid for all n greater equal 0.

So now, we multiply by z to the n and sum on n.

Sum n greater than equal to 0, A to the n, z to the n.

That's our generating function, A(z), that we're going to use to represent this

sequence a sub n. For the first term on the right-hand side

it's sum an - 1, z to the n. Change n to n1 + 1 throws out A(z).

So that's 5zA(z). And for the second term we change n to n

plus 2 in the, in the sum and throw out Az^2 that's minus 6z^2, a of z.

And the kronecker delta term, that's sum all n but that thing is only

one when n = 1. So, that's z to the n, in that case, is just z.

So that's an equation that generating function has to satisfy.

and that's a, [COUGH] easy equation to solve with some

algebra. so that is, it's just A of z is just z

over 1 minus 1 - 5z + 6z^2. that's again equation that, that generic

function has to satisfy. so, that's generating function, now we

want to extract coefficients because our goal is to find an expression for an.

so how we are going to extract coefficients?

Well, in the case of ratio of two polynomials, it's not difficult it's

technique knows as partial fractions where we factor the polynomial and the

denominator. and we know that our solution must be at

this form, because if you cross multiply then in the denominator, you get the

right polynomial because you've factored it.

And then, the numerator you've got two equations and two unknowns you have to

have c0 + c1 = 0 and you have to have the 2c0 + 3c1 = -1.

So that is, those unknowns have to satisfy those two simultaneous equations

and that's just what we got before and the solution is z0 = 1 and z1 = -1.

and so, that now expresses the generating function as a difference between two

geometric sums and those we know how to expand, it's 3 to the N minus two to the

N. So that's step by step given a recurrence

we can get the solution that is a simple expression for the coefficients and

that's going to work in every case. Now, there's complications that arise.

Let's look at a more complicated example. sometimes and, and this works for

actually any linear recurrence, because you get a polynomial and you can always

factor a polynomial. So, so let's look at this one, 5 an minus

1 minus 8 an-2 plus 4n-3. Same procedure to make these initial

conditions satified. I start at 0 and work up and find that I

have to add a delta n1 and a minus delta n2 in order to make it valid for all

that. Then, when you multiply by z to the n and

sum on end you get this equation on the generating function.

5zA(z) - 8z^2A(z) + 4z^3A(z)3 + z - z^2.2.

And again, now just using algebra, now we have an explicit expression for the

generating function. It's the ratio of two polynomials.

And ratio of two polynomials, partial fractions works, you have multiple terms.

in this case, there's the [COUGH] the root 1/2 has multiplicity 2

and that means just that, that polynomial

is I got three roots and then actually in this case one of the roots cancels with

the numerator so we have A(z) = z / (1-2z)^2 but that's one that we know,

that's a generating function that we already derived by differentiating the

geometrican scaling and that says that a sub n = n2^n-1.

Again, just algebra to find an explicit representation for the generating

function and then expand. now, it turns out that if you have roots

of multiplicity 3, you'll get terms of the form n^22, something to the n and so

forth. and there's other things that can happen,

but it's just properties of polynomials. so, for example, you could get complex

roots. So here's an example where the roots are

complex. Again, this is the same set up we have a third order linear equation

constant coefficients. we've got three initial conditions.

apply, do the deltas to make it valid for all n multiply by z^n n and sum on n and

then do algebra and then that gives a again a ratio of two polynomials.

The degree of the polynomial is equal to the degree of the recurrence.

in this case what happens is there is +z z^2 is one of the roots, one of the

factors of the [COUGH] denominator.

And again the numerator cancels so what do we do with 1 + z^2?

well, we can factor it with complex and find out that A(z) is a half, 1 / 1 - i

of z plus 1 over 1 plus i of z and we can go ahead and expand that and get this

representation. It's i to the n plus minus i to the n or

you can factor out an i to the n. and even though, i appears in this

solution if, when you do the math the

i never appears as a member of the sequence.

because when i is odd this thing cancels and when n is odd, this thing cancels to

0. and when n is even, then you go between 1

and -1 between because of the i^22 or i^4.4.

so that's a rather strange oscillating sequence, but it comes out immediately

from our process of our algorithmic process of finding sequence corresponding

to a given recurrence. It's a nice example, because it shows the

origin of the oscillations that we often see when we're studying algorithms or

combinatorial structure. Those oscillations are modeled in

mathematics really, in this case, by just the square root of -1.

square root of -1^2 is -1, and to the fourth power is +1, and that's

really reflected in this sequence. and it's going to be maybe not so easy to

uncover oscillations without using complex and as we'll see complex analysis

plays a fundamental role in analytic combinatorics when we get into advanced

methods. [COUGH] okay.

So here's a summary. and then, this is just a math with

unknowns just so we can state a theorem. And it's kind of a complicated looking

theorem, but next time we'll show that we don't really need all this detail.

but it's worthwhile to fully state this theorem, because the method that we've

talked about really leads right to a proof of this theorem that's not that

abstract. it's just a matter of turning the crank.

So what we know is that if you've got a [INAUDIBLE] order linear recurrence with

constant coefficients so that you just have [INAUDIBLE] terms on the right-hand

side. It's going to be a linear combination of

t terms. and it depends on the roots of the

polynomial that's induced by what happens when you get, when you multiply by

[INAUDIBLE] and do the algebra. You're always going to get this

polynomial, 1 - x1 minus like that in the

denominator. and it depends on the multiplicity of

those roots so if you've got r roots, where the multiplicity is m sub i.

So if you add up all the multiplicities you get t, then your solution is

depending on the multiplicity it's going to be, for every root you got a the, that

root to a power plus n times that root to a power all the way up to the, the

multiplicity and that has a total of t terms.

and again I'm not expect, not expecting people to follow really every detail of

this, but, you, you can get the idea that we can, actually write down a full

solution to linear recurrence and generating functions give us this proof.

And the constants involved can always be determined from the initial conditions

and that's using partial fractions and solving simultaneous equations.

And again, this is all automatic and people have implemented this process in

symbolic algebra systems. so actually, nowadays you can type in

recurrences and get the solution. and don't forget, your solution might

introduce, might involve periodic behavior that's introduced by the complex

roots, so it might not be the case to prove to be able to prove that even a

recurrence like this converges to a limit.

but it's all very straightforward and well understood mathematically.

Now, what about the analysis of algorithms?

For quicksort, we had this rather complex recurrence that was our starting point

for the analysis of quicksort. Can we use generating functions to solve

the quick sort recurrence? and, and the answer of course is that we

can. to make life easiest, we'll first

multiply both sides by n, although you can get it done without doing that.

so now we have a recurrence where we're not dividing by n and then multiply by Z

to the N, and sum. over now we sum for N bigger than or

equal to 1 and that's just because the CK-1 to

save us a few terms. so that's multiplying by Z to the N and sum and now

we got to look at each one of the terms and see what we have.

what do, what do we have on the left there? well, if we define the generating

function for the sequence of interest to be C of Z equals sum C sub n, Z to the N.

That is if you differentiate that multiplied by Z, that's what you get.

So that one is C prime of Z and there's a factor of Z all the way through that's

divided out. This one is two

[COUGH] 2z over 1-EQ. and again that's right out of the table.

and then a factor of z divides out. And this one is a convolution, it's 1 / 1

- z * z of z. so I, I skipped just a very few steps

here involving indexes that go to 0 and involving dividing by z.

But you can convince yourself quite easily that that ordinary differential

equation is the result of the [COUGH] simply evaluating the sums to get the

equation that the generating function has to satisfy.

So, that's ordinary differential equation and it's completely well, well-defined

and so now we need to know about solving differential equations, to get this

solved, and I don't want to give a course on solving differential equations.

I just point this out as an example for people who do know that

it's possible to solve it just by considering the equation without the

extra term. and figuring out that, what you need to

do is, solve that prob, that problem. in that case, that problem, the solution

is 1 / 1 - z^2.2. so if we didn't have this constant term,

the solution would be 1 / 1 - z^2. [INAUDIBLE] differentiate that, it's the

same thing as if you multiply by one over one - z and multiply by 2.

and then, what you do is multiply, by that, or divide by that factor, which

wides up by multiplying. and it's really, actually analogous, and

it is totally analogous to what we did when solving for sorted linear

reccurences, where we try to find something to multiply it by to make it

that a telescope, this is kind of similar. and this comes out to be a

simple equation in terms of the function, 1 / 1.

z^2, c of z. so if you differentiate that you get this

thing so and that's then equivalent to our equation.

so two that's 2 over 1-z and now, we can just integrate that simple thing if that

shows that c of z times order 1-c squared is equal of n of all of that which is two

log over 1-z and that's a solution. and so that's solving the differential

equation to get an explicit representation for the generating

function. not too bad.

It's a standard differential equation. And now, we want to extract coefficients

to find the number of compares taken by quicksort, but that's easily done. we've

seen that one that's the example that we did for an

exercise. It's 2 N plus 1, H N plus 1 minus 1.

So, OGFs can solve recurrences even as

complicated as the quicksort recurrence. there's many other examples of solutions

of recurrences using OGFs in the book.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play