Knuth · Weeks 29 to 63

TAOCP Volume 1: Fundamental Algorithms

Welcome to Knuth. Volume 1 starts with a big block of math (induction, sums, binomial coefficients, generating functions, asymptotics), then MIX, Knuth's imaginary computer and its assembly language, then the data structures everything else is built on: lists, trees, garbage collection and memory allocation. The math weeks are the hardest stretch of the whole path for most people. That is normal. Push through them and the rest of Knuth opens up.

35weeks

38reading guides

932exercises

~240hours

Every section, week by week

Section	Week	Exercises	Picked	Time
1.1 Algorithms	29	9 (10 to M30)	4	6 h
1.2.1 Mathematical Induction	30	15 (05 to 50)	8	6 h
1.2.2 Numbers, Powers, and Logarithms	31	29 (00 to M30)	8	4 h
1.2.3 Sums and Products	32	47 (M00 to M30)	8	8 h
1.2.4 Integer Functions and Elementary Number Theory	33	49 (00 to HM46)	8	7 h
1.2.5 Permutations and Factorials	34	25 (00 to M28)	8	5 h
1.2.6 Binomial Coefficients (part 1)	35	68 (00 to HM35)	8	7 h
1.2.6 Binomial Coefficients (part 2)	36	68 (00 to HM35)	8	8 h
1.2.7 Harmonic Numbers	37	24 (01 to M33)	8	4 h
1.2.8 Fibonacci Numbers	38	42 (10 to M38)	8	5 h
1.2.9 Generating Functions	39	26 (M01 to M40)	8	8 h
1.2.10 Analysis of an Algorithm	40	23 (10 to HM38)	8	7 h
1.2.11 Asymptotic Representations	41	42 (HM01 to HM42)	8	8 h
1.3.1 Description of MIX	42	26 (00 to 32)	8	7 h
1.3.2 The MIX Assembly Language	43	23 (00 to M47)	8	8 h
1.3.3 Applications to Permutations	44	36 (02 to HM42)	8	8 h
1.4.1 Subroutines	45	7 (10 to 26)	6	5 h
1.4.2 Coroutines	46	7 (10 to 30)	6	4 h
1.4.3 Interpretive Routines	47	15 (10 to 40)	8	8 h
1.4.4 Input and Output	48	19 (05 to 40)	8	4 h
1.4.5 History and Bibliography	48			1 h
2.1 Introduction	49	9 (04 to 23)	7	3 h
2.2.1 Stacks, Queues, and Deques	49	14 (00 to M48)	7	5 h
2.2.2 Sequential Allocation	50	19 (10 to HM43)	8	7 h
2.2.3 Linked Allocation	51	30 (10 to M48)	8	9 h
2.2.4 Circular Lists	52	18 (10 to M28)	8	5 h
2.2.5 Doubly Linked Lists	53	12 (20 to 40)	7	7 h
2.2.6 Arrays and Orthogonal Lists	54	24 (11 to 33)	8	7 h
2.3.1 Traversing Binary Trees	55	37 (00 to HM41)	8	9 h
2.3.2 Binary Tree Representation of Trees	56	22 (15 to M40)	8	7 h
2.3.3 Other Representations of Trees	57	19 (15 to 40)	8	7 h
2.3.4 Basic Mathematical Properties of Trees (part 1)	58	49 (M10 to HM40)	8	7 h
2.3.4 Basic Mathematical Properties of Trees (part 2)	59	54 (10 to HM40)	8	8 h
2.3.5 Lists and Garbage Collection	60	12 (00 to M30)	8	9 h
2.4 Multilinked Structures	61	15 (00 to 28)	8	6 h
2.5 Dynamic Storage Allocation	62	44 (00 to HM50)	8	9 h
2.6 History and Bibliography	63			1 h
Vol 1 review	63	932 (00 to HM50)	8	6 h

Each section links to its reading guide: what it covers, how to approach it, exercises picked from the book with their ratings, common traps and links. Picked is how many exercises the guide recommends; time is its budget for the week.

What you will be able to do

Analyze an algorithm exactly, not just in big-O: best case, worst case, average and variance.
Manipulate sums, binomial coefficients and generating functions with confidence.
Read and write assembly for a simple machine and count the cost of every instruction.
Implement linked structures, tree traversals, topological sort, a garbage collector and a malloc-style allocator from first principles.

Before you start

Finished Crafting Interpreters (you will see the same ideas again in 1.4.3, 2.3.5 and 2.5).
High-school algebra and comfort with proofs by induction (Week 0 math covers it).
Basic calculus helps for 1.2.9 and 1.2.11; you can skim the heaviest parts.
A MIX simulator such as GNU MDK.

Getting the book

The current edition is the third edition (1997), ISBN 0-201-89683-4.

TAOCP is not free. Vol 1, 3rd edition is about $64 new from InformIT (the publisher's store) and much less used. Borrow before you buy: many public and university libraries give you free access to O'Reilly Learning, which carries TAOCP; Libby/OverDrive and interlibrary loan (search WorldCat) work too. Older used editions are fine for Vols 1 to 3; section numbers barely changed. If you buy the eBook, get the PDF from InformIT. Knuth himself warns that the Kindle and ePUB versions mangle the math.

What you need has every option with prices, and which edition do I need covers the differences.

Tips

Read the front matter on exercise ratings before 1.1. You will use that scale for two years.
Keep a notebook of identities and tricks; you will refer back to it in every later volume.
Concrete Mathematics (Graham, Knuth, Patashnik) is the best companion if 1.2 feels too terse.
Expect to not finish every exercise. Nobody does. The guides tell you which ones matter.

Questions

How long does TAOCP Volume 1 take?

On the cracked.guide path it takes 35 weeks (weeks 29 to 63), about 8 months, and the reading guides budget about 240 hours in all.

How many exercises are in TAOCP Volume 1?

932 in the sections the path covers, rated 00 to HM50, and 273 of them carry Knuth's triangle for recommended. Each reading guide picks the ones worth your time.

Which edition of Volume 1 do I need?

The current one is the third edition (1997). Older used editions work for most of it; section numbers barely changed. Buy the PDF, not Kindle, if you want an eBook.