TAOCP 1.1 Algorithms: reading guide

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).