Foundations to FrontierPart IX: The graduate coreBezhig

W08: Defending an independent engineering result

5 exercises, each with a complete solution.

On this page
  1. Prerequisites and observable goals
  2. The central question: could another engineer challenge and reproduce this result?
  3. A complete worked review: a proposed spatial-query improvement
  4. How to move from guided work to an independent defense
  5. A portfolio artifact another engineer can inspect
  6. Independent practice
  7. Complete solutions: W08
  8. Retention and readiness

Prerequisites and observable goals#

Before

The core assessments, one completed J project, and relevant G chapters; use GP1 or GP2 for a deeper exemplar.

After

Combine specification, mathematical reasoning, implementation, tests, and measurement in one defensible report; diagnose changed assumptions instead of relying on familiar patterns.

The central question: could another engineer challenge and reproduce this result?#

A mature technical result is not a code dump, a numerical answer, or an attractive chart. It is a chain of claims with evidence at each link: what problem was specified; why the method is appropriate; what the implementation actually does; how it was tested; what was measured; and what remains uncertain. This final workshop asks you to assemble that chain. It does not introduce an eighth large project or count every report subsection as a new assignment.

Choose a bounded claim. “My engine is faster” is too broad. “For immutable two-dimensional point snapshots with this query distribution and identical inclusive box outputs, the spatial index reduces candidate checks relative to a full scan” is testable. “This model is intelligent” is too broad. “On a held-out group split drawn from this synthetic fixture, this frozen classifier achieved these confusion counts at a threshold chosen without using the test labels” identifies data, policy, and limitations.

A complete worked review: a proposed spatial-query improvement#

Suppose an implementation places points in square cells of side s>0s>0, computes each cell as (⌊x/s⌋,⌊y/s⌋)(\lfloor x/s\rfloor,\lfloor y/s\rfloor), and returns all point IDs from cells touched by a requested axis-aligned box. The author says the result is correct because every point in the box belongs to a touched cell, and reports tenfold acceleration over a scan.

First inspect the contract: are box bounds ordered and inclusive, are IDs unique, and can coordinates be negative? The coverage argument addresses false negatives, but not false positives. A touched cell may extend outside the exact box. Returning every candidate therefore violates an exact containment contract. Add the final coordinate comparisons. Test negative coordinates specifically: truncation toward zero is not floor for negative fractions and would change the bucket geometry.

Second inspect the benchmark: do both versions sort output IDs, validate input, include index construction, and return exactly the same set? A faster candidate superset is not the same task. Index construction may be amortized across many queries, but that assumption must be written; a one-query workload may favor the scan. A huge sparse box can cause many empty-cell probes, requiring a fallback or a bounded-work policy. A dense cluster can collapse selectivity even when average behavior looks excellent.

Third inspect concurrency: an immutable snapshot with preallocated disjoint output slots and joined workers supports a clean ownership argument. Concurrent index mutation requires a different consistency and lifetime design. A stress test that passes does not establish that unguarded shared mutation is safe. The theorem about geometric coverage and the theorem about access safety are separate premises of the whole result.

A revised claim might be: “Under immutable input, finite coordinate limits, exact final containment, and this measured query distribution, the indexed implementation produces the same sorted IDs as the reference scan. Candidate counts and repeated timings were recorded separately; index-build cost is excluded because one build serves the stated batch. Clustered and sparse-large-query cases are reported as limitations.” That statement is narrower but far more useful. J05 provides the complete bounded implementation and G06/G16 sharpen the measurement reasoning.

How to move from guided work to an independent defense#

Preserve your first implementation and its failures. Build a simple correctness oracle before an optimized implementation when practical. Derive at least one property that tests can check across generated inputs, such as conservation, monotonicity, idempotent replay, or equivalent outputs. Also construct an adversarial case designed to break your assumptions. A large random suite may rarely generate an important boundary, and two implementations sharing the same helper can share a bug.

Write an invariant, recurrence, residual condition, or semantic argument appropriate to the task. A proof should state its domain and connect to the actual representation. For example, a mathematical integer sum is not a proof about overflowing signed C++ arithmetic. A least-squares optimum is not a proof that the training/test split was fair. A deduplicated consumer effect is not a proof that every message is eventually delivered despite infinite failures.

Then measure a correct fixed contract. Identify what is timed, choose representative workload families, keep raw measurements, alternate comparison order, and report distributions instead of a best single run. Analyze memory and complexity separately from wall-clock time. When results are inconclusive, report that; selecting a favorable sample after seeing the data changes the question.

Finally, explain the result to another person without the reference open. Be able to defend a rejected alternative, a failure case, and a tradeoff. When asked to change a requirement, update the reasoning before patching the code. This is where the mathematics, theory, and engineering modules become one ability rather than a list of topics.

A portfolio artifact another engineer can inspect#

A useful project directory contains a concise problem statement; supported environment and clean build commands; synthetic or appropriately licensed fixtures; separate tests; design rationale; the key proof or model assumptions; reproducible measurement commands and raw results; known limitations; and a contribution record. The contribution record distinguishes personally designed and implemented work from libraries, copied examples, AI-assisted drafts, or reference code studied afterward. Honest attribution makes independent strengths visible rather than weakening them.

For research preparation, add a focused question and a prior-work comparison. State what would falsify your hypothesis and whether your experiment actually tests it. Replicating a known result is valuable training but not automatically novel research. A new observation with insufficient controls is a lead for investigation, not an established theorem. G16 provides a route to increasingly independent paper reading and experimentation.

Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

W08.01TSolution

A spatial index uses integer truncation for negative cell coordinates and returns every candidate from touched cells. Write an exact inclusive-box contract, give a false-positive example, explain the negative-coordinate issue, and design correctness tests and a fair scan comparison. State which claims need a proof and which need a measurement.

W08.02TSolution

An asynchronous task captures a reference to a local vector and is allowed to finish after its function returns. It increments a shared ordinary counter, and a passing stress test is offered as proof of safety. Diagnose both defects and propose a design with explicit ownership, completion, and output policy. Discuss an alternative and its cost.

W08.03TSolution

A numerical model reports a small conservation error but predicts zero crossings increasingly late. It was tested at only one step size. Explain how both observations can occur, design a validation study that separates phase and amplitude behavior, and distinguish numerical validation from physical-model validation.

W08.04TSolution

A classifier has scores interpreted as calibrated positive probabilities. False positives cost 2 units and false negatives cost 8 units, with correct decisions costing zero. Derive the cost-minimizing threshold under those assumptions. Then design a leakage-resistant evaluation and retry-safe recording workflow, including a model-identity rule and an explicit human-impact limitation.

W08.05TSolution

Prepare a one-page independent-defense outline for either GP1 or GP2, then respond to a changed requirement: GP1 now allows mutable external calls, or GP2 must permit multiple model versions concurrently. Identify what proof, data contract, tests, and performance measurements must change. Provide one concrete example that defeats a naive patch.

Optional small hints

For .01, prove both inclusion directions. For .02, count object lifetime and data race as different questions. For .04, compare expected costs conditional on a score, not the class base rate alone. For .05, a requirement change can invalidate the original theorem even when all old tests pass.

Complete solutions: W08#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

W08.01Show solution

Specify exact output before optimizing candidates

One contract: for finite unique-ID points and finite ordered bounds (ℓ,b,r,t)(\ell,b,r,t), return each ID exactly once precisely when ℓ≤x≤r\ell\le x\le r and b≤y≤tb\le y\le t, in sorted ID order. A cell spanning [0,1)×[0,1)[0,1)\times[0,1) touched by box [0,.1]×[0,.1][0,.1]\times[0,.1] may contain point (.9,.9)(.9,.9); returning that candidate is a false positive. The final exact predicate is necessary.

For x=−.2x=-.2 and cell size 1, floor yields −1-1 while truncation yields 0. A scheme whose enumeration bounds assume floor but whose insertion truncates can miss points or search the wrong geometric cells. Consistent truncation can define a different bucket partition, but the floor-based coverage proof would no longer apply without revision. Do not claim every use of truncation necessarily fails every possible index; identify the mismatched contract.

Tests should include negative coordinates, exact cell/box boundaries, empty inputs, duplicate-ID rejection, clustered points, huge sparse boxes, tiny boxes, and randomized comparison against a simple exact scan. Prove every true hit is visited and every emitted ID passes containment, with unique IDs and no double emission. Prove safe range arithmetic separately. For performance, fix identical output sorting and validation, record index-build inclusion, query distribution, candidate/hit counts, raw repeated timing, and input sizes. Coverage is a mathematical claim; the speed advantage is empirical and workload-specific.

Back to W08.01
W08.02Show solution

Lifetime and synchronization both need a contract

The referenced vector dies when its owning local scope ends, so a later task dereferences an object outside its lifetime. Independently, concurrent increments of a shared ordinary counter can be a data race; a familiar lost-update trace is not a complete description of undefined C++ behavior. A passing stress test establishes neither property.

A safe bounded design may move the vector into task-owned storage, preallocate result slots, assign each task a disjoint slot, join or otherwise await completion before consuming results, and aggregate counts afterward in one thread. Read-only sharing can use an immutable object with an ownership mechanism ensuring its lifetime extends beyond all tasks. A counter needing concurrent updates can use a correct atomic read-modify-write or a mutex, with the memory-order requirement determined by whether it publishes other data. An alternative is copying input per task; it simplifies lifetime but increases memory and copying cost. An alternative is synchronous completion before returning; it simplifies ownership but changes latency and scheduling. Specify error propagation and cancellation so a failed task does not leave an apparently complete result.

Back to W08.02
W08.03Show solution

An invariant does not locate the correct point on an orbit

A method can stay near an energy surface while traversing it at a slightly wrong frequency. Bounded amplitude and accumulated phase error are compatible. The Verlet analysis in W05 demonstrates a numerical frequency different from the continuous one even in a stable regime. Compare trajectories to analytic position and velocity at common times, measure zero-crossing or period error with a documented interpolation method, and study energy and maximum state error separately. Use several halved steps over both short and longer fixed intervals, preserving initial conditions and parameters. Check whether errors scale as expected before roundoff dominates.

Physical-model validation additionally requires evidence that the equations, forces, parameters, and measurements describe the real system. Converging accurately to a damping-free oscillator cannot validate a damped physical device. Explain model discrepancy, measurement uncertainty, discretization, and finite precision as different uncertainties; a small energy error alone quantifies none of the others.

Back to W08.03
W08.04Show solution

A decision policy is not just a probability model

For calibrated p=P(Y=1∣available information)p=P(Y=1\mid\text{available information}), predicting positive has expected cost 2(1−p)2(1-p) and predicting negative has expected cost 8p8p. Choose positive when 2(1−p)≤8p2(1-p)\le8p, equivalently p≥.2p\ge.2. A tie policy at .2.2 should be specified. The derivation assumes the stated costs, calibration for the deployment population, and zero cost for correct decisions. Capacity constraints, asymmetric downstream consequences, or changed prevalence/calibration can change the policy.

Split by independent entity and relevant time before fitting preprocessing. Fit transforms on training data only, choose model and threshold with validation evidence, freeze the artifact and policy, then evaluate the untouched test set with confusion counts, calibration, group/sample limitations, and expected cost under the declared policy. Do not tune on the test result and keep calling it untouched.

For recording, include immutable input and model/policy digests in a canonical job payload. Atomically record a producer job with its outbox item; have the consumer commit receipt and effect together, reject an ID reused with a different payload, and acknowledge only after consumer success. A crash after consumer commit can cause delivery repetition but must not duplicate the matching result. Tests should terminate a worker at that boundary and reopen both stores. These are local process-crash claims, not proof against power loss or arbitrary distributed failure. Human-impact use additionally needs consent/data governance, domain validation, review and appeal, and monitoring; calibrated scores and a cost equation do not decide whose harms are acceptable.

Back to W08.04
W08.05Show solution

A changed requirement revises the theorem

An adequate GP1 defense states the accepted pure language, lexical binding semantics, type rules, compiler/VM relation, verifier invariants, resource bounds, test strategy, and limitations. With mutable external calls, rewriting 0⋅e0\cdot e to zero can remove an effect: if ee increments a counter, the optimized and original programs differ observably. Repeated evaluation or reordering can also change outputs. Add an effectful semantics and effect-aware transformations, define ordering and exceptions, change bytecode/type or effect checks, and test observable traces rather than return values alone. The original pure-language induction is not enough.

An adequate GP2 defense states training/validation/test separation, immutable model schema, data and policy identity, producer/consumer transactions, replay behavior, crash boundary, and local durability limits. Concurrent versions require a versioned artifact registry and a rule binding each job to one exact digest, not “whatever model is newest.” A naive patch that loads the latest artifact on retry can record a different prediction after a crash, violating the original job identity. Tests should submit jobs with two versions, retry them across deployment changes, reject unavailable or mismatched digests, and compare each recorded result against its bound version. Define retention of old artifacts, authorization, schema migration, and throughput/storage costs. Passing all old single-version tests would not establish these new conditions.

Both outlines should include a reproducible build, original unaided work, a failing example and repair, independent test oracles, raw measurements where performance is claimed, and a precise account of personal contribution. Multiple designs can be valid; the required common feature is that the changed assumption is reflected in the reasoning, implementation, and evidence.

Back to W08.05

Retention and readiness#

Return to this workshop after a month with a different project or changed requirement. A strong independent answer identifies the first invalid assumption, constructs a small counterexample, proposes a bounded repair, and explains what evidence would support it. That is progress toward reliable engineering, not merely recognition of the solution you just read.