Week 96 of 125
TAOCP 6.3 Digital Searching
Sign up or sign in to tick these off and give this week a due date.
-
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.