Week 66 of 125
TAOCP 4.5.3 Analysis of Euclid's Algorithm
Sign up or sign in to tick these off and give this week a due date.
-
How many steps Euclid takes: the worst case involves consecutive Fibonacci numbers (Lame's theorem), and the average case connects to continued fractions and a famous distribution of partial quotients.
Time About 8 hours this week
Why it matters
A beautiful example of algorithm analysis meeting deep math. The worst-case result alone (logarithmic steps) is worth knowing cold.
Before you start
- 4.5.2 The Greatest Common Divisor
- 1.2.8 Fibonacci Numbers
How to approach it
Prove the Fibonacci worst case yourself first. Then empirically count steps on random inputs and compare to the average formula. The heavy continued-fraction analysis can be read for ideas.
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
- Getting lost in the HM material. The first part is the essential part.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.