TAOCP 4.7 Manipulation of Power Series: reading guide

Algorithms for working with power series as data: multiplying, dividing, raising to powers, composing and reversing them, including Lagrange inversion.

Time About 5 hours this week

Why it matters

This is computer algebra territory, and it is the algorithmic side of the generating functions from 1.2.9. Useful if you ever do combinatorics by computer.

Before you start

1.2.9 Generating Functions
4.6 Polynomial Arithmetic

How to approach it

Implement power-series multiplication and reciprocal on truncated series. Use them to compute the Catalan numbers from their generating function.

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

Forgetting to truncate, which makes costs explode.