TAOCP 6.1 Sequential Searching: reading guide

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.