Week 25 of 125
TAOCP 1.2.9 Generating Functions
Sign up or sign in to tick these off and give this week a due date.
-
Treating a whole sequence as the coefficients of a power series, then manipulating the series (adding, shifting, multiplying, differentiating) to solve recurrences and evaluate sums.
Time About 8 hours this week
Why it matters
Generating functions are the single most powerful tool in algorithm analysis. Everything from counting binary trees to averaging hashing costs uses them.
Before you start
- 1.2.8 Fibonacci Numbers
- Basic calculus (derivatives, geometric series)
How to approach it
Make a table of the basic operations (shift, multiply by z, differentiate, convolution) and what each does to the coefficients. For each worked example, close the book and redo it. If it does not click, Concrete Mathematics chapter 7 and Wilf's free book generatingfunctionology are excellent companions.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Worrying about convergence. Knuth mostly treats these as formal power series, so you can manipulate first and ask questions later.
- Forgetting the convolution rule; it is the one you will use most.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.