Week 99 of 125
TAOCP 6.5 and Vol
Sign up or sign in to tick these off and give this week a due date.
-
Searching on attributes other than the primary key: inverted files, multi-attribute queries, range and partial-match queries, and superimposed coding (the idea behind Bloom filters).
Time About 7 hours this week
Why it matters
Inverted indexes power every search engine, and Bloom filters are everywhere from databases to network caches.
Before you start
- 6.4 Hashing
How to approach it
Build a tiny inverted index for a folder of text files and answer AND queries. Implement a Bloom filter and measure its false positive rate.
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
- Picking the number of Bloom filter hash functions without doing the math.
-
Knuth Knuth Vol 3 review
A review week for Volume 3: sorting and searching.
Time About 6 hours this week
Why it matters
This is the most directly practical volume. Consolidating it gives you a reference you will use for the rest of your career.
Before you start
- All of Vol 3
How to approach it
Gather your implementations (quicksort, heapsort, merge sort, radix sort, BST, AVL, B-tree, hash tables) in one repo with a shared benchmark harness. Write a short decision guide: which sort or search structure when.
Exercises
Redo one sorting analysis from 5.2 from scratch without looking.