Week 34 of 125
TAOCP 2.1 and 2.2.1
Sign up or sign in to tick these off and give this week a due date.
-
Knuth Knuth 2.1 Introduction
Chapter 2 opens by defining how Knuth represents data in memory: nodes made of fields, links (pointers), and the notation he uses for them. It walks through a small example with a pile of playing cards.
Time About 3 hours this week
Why it matters
This notation is used for the rest of the series. It also forces you to think about data as concrete memory layout, which is exactly what C taught you in clox.
Before you start
- 1.3 MIX
How to approach it
Short and important. Learn the node and field notation until you can read it without thinking. Relate it to C structs and pointers.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.
Traps
- Mixing up a link and the node it points to in Knuth's notation.
-
The three classic linear structures defined by where you insert and delete. Knuth uses railway-switching pictures to explore which output orders a stack or deque can produce from a given input order.
Time About 5 hours this week
Why it matters
Stacks and queues are the backbone of parsers, schedulers and graph search. The question of which permutations a stack can produce is a classic interview-style puzzle with a beautiful answer.
Before you start
- 2.1 Introduction
How to approach it
Draw the railway diagrams and push cars through them by hand. Then write a quick program that lists all permutations of 1..4 a stack can produce and count them. Compare with the Catalan numbers.
Exercises
Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.
Traps
- Confusing an input-restricted deque with an output-restricted one.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.