Week 17 of 125
TAOCP 1.1 Algorithms
Sign up or sign in to tick these off and give this week a due date.
-
Knuth Knuth 1.1 Algorithms
Knuth opens with Euclid's algorithm for the greatest common divisor and uses it to pin down what an algorithm actually is: finite, definite, with input, output and effective steps. He also introduces his house style for writing algorithms as lettered, numbered steps, and sketches a formal model of computation at the end.
Time About 6 hours this week
Why it matters
Every later section uses this step-by-step format, so getting comfortable with it now pays off for 100+ weeks. The five properties are also a decent checklist for any spec you write at work: if a step is not definite or not guaranteed to terminate, you have a bug waiting to happen.
Before you start
- Comfort reading pseudocode
- Remainders and division (week 0 math)
How to approach it
Before the section itself, read the front matter "Notes on the Exercises" carefully: it explains the rating scale (00 to 50, M for math, HM for higher math, the triangle and arrow markers) that you will rely on for the next two years. Then trace Algorithm E by hand on a few pairs of numbers until it feels boring. Read the five properties slowly. The last few pages on a set-theoretic definition of computation are fine to skim on a first pass; come back to them later if you are curious.
Exercises
The exercises here are friendly; do all of the low-rated ones. If you want a stretch, try the M-rated ones near the end that connect Euclid to more formal models, but do not let them eat the week.
- Exercise 1 10 Rearranging four variables using only replacement steps. A tiny warm-up that forces you to think about the order of assignments, the same thing that bites people in swap code.
- Exercise 2 15 A short proof about the relationship between m and n at step E1. Good first practice at reasoning about an algorithm's state instead of just running it.
- Exercise 3 20 Rewrite Euclid's algorithm to avoid trivial copy steps. This is your first "improve the algorithm in Knuth style" exercise and it is very doable.
- Exercise 4 16 Compute a gcd by hand with Algorithm E. Pure mechanics, but it locks in the steps.
Traps
- Getting stuck on the formal definition at the end of the section. It is optional on a first read.
- Treating the exercise ratings as difficulty for you personally. They are Knuth's estimate of time for a prepared reader; a 20 can take you an hour early on and that is normal.
- Buying an old edition by accident. You want Vol 1, 3rd edition (1997, with later printings).
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.