Week 68 of 125
TAOCP 4.6.1 Division of Polynomials
Sign up or sign in to tick these off and give this week a due date.
-
Polynomial arithmetic, especially division with remainder, and computing greatest common divisors of polynomials, including variants that avoid fractions when coefficients are integers.
Time About 7 hours this week
Why it matters
Polynomials over finite fields power error-correcting codes, CRCs and cryptography. Polynomial gcd is a building block in computer algebra.
Before you start
- 4.5.2 The Greatest Common Divisor
- 4.3.1 Classical Algorithms
How to approach it
Implement polynomial division over integers mod a prime. Then compute a CRC by hand as polynomial division over GF(2) to see a real use.
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
- Coefficient blow-up when working over the integers. That is exactly what the fraction-free methods address.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.