Week 18 of 125
TAOCP 1.2.1 and 1.2.2
Sign up or sign in to tick these off and give this week a due date.
-
Induction as the main tool for proving things about integers and about programs. Knuth goes further than a typical math class by showing how to prove an algorithm correct by attaching assertions to each step of a flowchart, using an extended version of Euclid's algorithm as the worked example.
Time About 6 hours this week
Why it matters
Loop invariants, the thing that makes binary search and in-place algorithms correct, are induction in disguise. Once you can write the invariant, debugging off-by-one errors gets a lot less random.
Before you start
- 1.1 Algorithms
- Basic induction proofs (week 0)
How to approach it
Read the basic induction material quickly if you have seen it before. Slow way down for the flowchart-with-assertions proof of the extended Euclid algorithm: copy the flowchart onto paper and check every assertion yourself, step by step. That technique is the payoff of the section.
Exercises
Some of the early exercises hand you a "proof" that looks fine but proves something false; find the hole before reading the answer, it is great training for code review. 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 the base case or proving the step only for large n.
- Strengthening the hypothesis is often the trick: if the induction step will not go through, try proving something stronger.
- Reading the assertion proof without actually checking each arrow. You will not absorb it passively.
-
A careful build-up of integers, rationals and reals, then powers with real exponents and logarithms in any base. It ends with practical ways to compute logarithms by hand-style methods.
Time About 4 hours this week
Why it matters
Logs are everywhere in complexity analysis, bit counts and data sizes. Knowing exactly how log base changes work, and why lg n and ln n differ only by a constant, makes big-O arguments feel obvious instead of magical.
Before you start
- High-school algebra
- Exponent rules
How to approach it
Skim the construction of the real numbers unless you enjoy it. Work through the logarithm identities with pencil and make a cheat sheet of lg, ln and log10 conversions. Try the method for computing a logarithm digit by digit on a small example.
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
- Mixing up lg (base 2), ln (base e) and log10. Knuth uses lg for base 2 throughout the series.
- Spending the whole week on the real-number construction. It is background, not the point.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.