Week 72 of 125
TAOCP 4.7 and Vol
Sign up or sign in to tick these off and give this week a due date.
-
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.
-
Knuth Knuth Vol 2 review
A review week for Volume 2: random numbers and arithmetic.
Time About 5 hours this week
Why it matters
Vol 3 leans on probability (from chapter 3) and on the analysis style you practiced. A quick review makes the switch smoother.
Before you start
- All of Vol 2
How to approach it
Tidy up the code you wrote: PRNGs, tests, bignums, gcd, factoring. Put it in one repo with tests. Write a one-page summary of what to use in practice for random numbers and for big arithmetic.
Exercises
Finish one programming exercise you started and abandoned.
Traps
- Skipping review. This is the halfway point of the whole path.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.