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.
Solving Recurrences
Loading...
En provenance du cours de Princeton University
Analysis of Algorithms
32 notes
À 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.
Rencontrer les enseignants
Robert SedgewickWilliam 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.
© 2018 Coursera Inc. Tous droits réservés.
