CMP.10:4 - Solution

Name the operations → choose retained distinctions → construct representation and invariants → derive reads and updates → compare total work → use and revise the choice.

CMP.10:4.1 - Start from the operations and their conditions

List the operations needed by the computation, including their inputs and returned results. Distinguish membership, enumeration, selection by order, aggregation, insertion, deletion and value replacement when their requirements differ. Include whether answers need original identities or only values.

Describe the anticipated operation sequence or range of workloads. A fixed dataset with many queries differs from a changing stream. If the mix is unknown, compare alternatives over the plausible range instead of inventing one universal average.

State which resources constrain the work: storage, worst-case response, total running time, memory transfers or communication. Include the required output size; listing k distinct items takes work to produce those k items under an ordinary explicit-output model.

CMP.10:4.2 - Choose what the representation must distinguish

Define how a stored state represents the abstract object or the observations required of it. State the invariants that make reads meaningful. A sorted array needs an order invariant; an aggregate tree needs each stored aggregate to agree with the segment it represents.

If two source states share one representation, check every required read and continuation. Their equality must preserve the requested answers after the allowed updates. MATH.2 supplies identification under operations. If the representation is deliberately lossy, CMP.8 supplies the approximate answer relation.

Keep consequential identity, multiplicity and ordering. A set removes duplicates; a sequence retains positions. A zero numeric value need not mean an absent relation. An object reference and a copied value respond differently to later mutation.

CMP.10:4.3 - Construct operations from the representation’s structure

Choose a structure whose retained information makes the frequent operation cheaper. A sorted array supports binary search by repeatedly excluding one ordered half. A hierarchy of aggregates answers a range query by combining a small set of segments. Lists of actual neighbors avoid scanning absent graph edges.

Derive each read and update from the invariant. For an update, identify every stored part whose meaning depends on the changed input, and restore it. Include shared summaries and the operations used to recover an original witness. CMP.3 supplies reuse and dependency reasoning when values are cached across computations.

When summaries are combined, state the algebra the procedure needs. An associative operation permits regrouping; it need not permit reordering. An identity element can represent an empty segment. Inverses are required only for a method that subtracts or otherwise undoes an aggregate, not for every range-query construction.

For dynamic storage, include growth and rebuilding. Doubling an array’s capacity gives occasional linear copying and bounded total copying over a sequence of appends. The resulting amortized append cost does not claim constant worst-case latency for every individual append. A latency requirement can select incremental rebuilding or another representation.

CMP.10:4.4 - Count the complete computation under an explicit cost model

Compare construction and conversion, the intended reads and updates, reconstruction or output, and peak storage. A useful first comparison is construction cost + sum of operation costs for the workload. Keep several resource dimensions separate when no accepted trade-off combines them.

State what one elementary operation costs. Arithmetic on a bounded machine word can be treated as constant in an appropriate model; multiplying or comparing integers whose encoded lengths grow needs the corresponding bit cost. A symbolic expression that shares subexpressions can be small while its fully expanded output is large.

If transfers between memory levels dominate, analyze blocks moved as well as abstract pointer or arithmetic operations. A representation with contiguous access can outperform one with fewer but scattered accesses. Realization measurements can distinguish close candidates; they need not precede a decision already settled by an adequate cost argument.

Include invalidation and synchronization when shared updates are part of the workload. An operation that is correct in sequential use does not acquire a concurrent guarantee merely because its representation is shared.

CMP.10:4.5 - Compare alternatives at the receiving use

Construct the simplest credible alternative, not only a slower version of the favored structure. Compare raw storage with a precomputed index, full retention with reconstruction, or a compact representation with an expanded one according to the actual operations.

Require preservation of the needed answers before treating reduced cost as improvement. For a deliberate approximation, retain its qualified result and the loss it buys. Use the existing characterization, Pareto and improvement methods when choices trade storage, latency, update work and precision; no single representation must dominate every workload.

Select conversion only when its cost and risk are justified by the expected subsequent use. A mixed strategy can keep a simple base representation and add one index for the consequential query. Its update obligations remain part of the choice.

CMP.10:4.6 - Return a usable representation and reopen it locally

Return the structure, its meaningful state, read and update procedures, and the resource consequence that motivated the change. A small worked operation should expose the invariant and a consequential change should test its maintenance.

Reconsider the choice when the query mix, update pattern, output identity, data magnitude or physical access cost changes. Preserve the abstract object and valid algorithms where they remain applicable. A newly required distinction that the old representation discarded may require returning to the source data, not merely rebuilding an index from the insufficient summary.