Reading routes and prerequisites

The sidebar follows a suggested learning sequence: foundations and structures, spatial search, graph methods, optional extensions, then integrated applications. You can also follow a shorter route. The concept index supports individual questions. These routes show how the ideas build on one another.

For the course schedule, use the CS2040HS weekly reading map to match each teaching week with the relevant book topics.

Topic 9 follows BSTs and AVL trees to compare spatial invariants with one-dimensional ordering; AVL rotations do not generally preserve k-d-tree partitions. Topics 10–13 establish heaps, traversal and union–find before graph optimisation. Within Topic 13, only Kruskal requires the disjoint-set class. Spatial search is not a prerequisite for the graph route, and Topics 14–15 are optional extensions: the transport case in Topic 16 can be read directly after Topic 13.

Python is the reference for explanations and traces. Every code panel also offers JavaScript and Julia tabs; choose a language with a click or tap. Read the code language guide for indexing, mutation and download conventions.

A common reasoning thread¶

Each topic asks what the input means, which operations are required, what the representation stores, which invariant remains true, why the procedure finishes, and how work and live storage grow. Use the correctness checklist and cost model across the whole book.

Tie rules and boundary conventions are local contracts. Binary search can use inclusive or half-open intervals if its updates match. BSTs here keep distinct keys; k-d trees send coordinate ties right; priority queues use arrival counters when stable ties are wanted. Follow the stated convention rather than transferring a rule by name alone.

For current scope, conceptual-only coverage and future additions, see Coverage and extensions. Topic 16 now brings these ideas together through a complete fictional transport-network case.

Check your reasoning as you read¶

All sixteen topics use a self-reading format: two learning goals and prerequisite links at the start of each reading, then a misconception reminder and two prediction questions with expandable explanations. Predict a branch or result before opening the panel; use a mismatch to identify which boundary or invariant to revisit. These are ungraded, original examples.

The spatial sidebar groups k-d trees, point quadtrees, PR quadtrees and R-trees. Compare construction/insertion, exact lookup, range search, nearest search and deletion for each method. The R-tree range helpers precede the exact lookup that reuses them. Compare the cost summaries only after checking which code, occupancy assumptions, node visits and geometry tests each bound describes.

Plan study blocks around the work¶

Reading a definition, tracing a figure and understanding a complete class require different effort. The blocks below are suggested stopping places, not equal-duration lessons or measured reading-time estimates. Split a block again when you need to draw references, trace code or attempt the checks. Short method/contract pages often orient the longer implementation that follows.

On a first pass, state the contract and trace the supplied example. On a second pass, explain the invariant, implementation choices and full costs, then try the checks without the answers. Revisit prerequisite links when a trace fails; you do not need to restart an entire topic.

Read local contracts with a shared vocabulary¶

The brief ADT introduction and analysis conventions define these distinctions. Later pages make their particular result, tie, boundary and error policies explicit.