Week 91 of 125
TAOCP 6.1 Sequential Searching
Sign up or sign in to tick these off and give this week a due date.
-
Searching a list one item at a time, with tricks like sentinels to speed up the loop, and self-organizing lists that move frequently accessed items toward the front.
Time About 6 hours this week
Why it matters
For small arrays, linear search beats fancier structures. The sentinel trick and move-to-front heuristic are still used in real code.
Before you start
- Chapter 5 basics
How to approach it
Implement linear search with and without a sentinel and benchmark. Implement move-to-front on a Zipf-distributed access pattern and measure the average search length.
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
- Forgetting to restore the sentinel slot.