TAOCP 6.3 Digital Searching: reading guide

Searching by looking at keys digit by digit or bit by bit instead of comparing whole keys: tries, digital search trees, and Patricia, a compact trie for long keys.

Time About 8 hours this week

Why it matters

Tries and radix trees power autocomplete, IP routing tables, and in-memory indexes in many databases.

Before you start

6.2 Searching by Comparison of Keys

How to approach it

Implement a simple trie for words, then a compressed radix tree. Compare memory and speed with a hash set on a dictionary file.

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

Memory blow-up from fixed-size child arrays in each trie node.