Foundations to FrontierPart IV: Algorithms and systemsBezhig

Cumulative checkpoint: systems and engineering evidence

6 exercises, each with a complete solution.

Use after C09–C17. These questions intentionally mix representation, failures, safety, and evaluation. Work from assumptions rather than recalling a slogan. A design answer can have several valid implementations, but must preserve the stated invariant.

CS.01CSolution

Explain why signed C++ overflow, unsigned modular arithmetic, and mathematical integer addition are different. Give a reason a sanitizer run cannot replace defining the intended numeric domain.

CS.02TSolution

A worker waits with if (queue.empty()) cv.wait(lock); and then pops an item. Identify two reasons the condition may not hold after waking and state the correct predicate-based approach.

CS.03TSolution

A service commits a reservation but loses its reply. The retry uses the same key and a different quantity. What should happen under J03’s contract, and why would silently accepting the new quantity corrupt the meaning of retry identity?

CS.04TSolution

A system’s p95 latency improves after all failed requests are removed from the report. Explain why the comparison may be misleading and specify a more transparent reporting population.

CS.05TSolution

A parser validates JSON, then trusts a client field role="admin". Explain which boundary remains broken. Does adding TLS fix it? Distinguish syntax, authentication, and authorization.

CS.06TSolution

A team claims “verified across platforms, race-free, and 100 times faster” after one Linux sanitizer run and a selective single-threaded benchmark. Rewrite the claim into an accurate engineering report and name the missing evidence for each stronger assertion.

Optional small hints

CS.02: wakeups are not ownership transfers. CS.04: keep the population and failure rate visible. CS.06: report exactly the environment, checks, and workload that actually ran.

Complete solutions: CS#

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

CS.01Show solution

The representation is part of the specification

Mathematical integers are unbounded abstractions. Unsigned C++ arithmetic is reduced modulo the type’s range size. Signed overflow is not a defined wraparound operation in ordinary C++ semantics. A sanitizer can reveal selected executed violations, but it cannot decide whether the application intended exact arithmetic, checked bounded arithmetic, saturation, or modular behavior. Define that domain first, then choose types and checks that implement it. Unexecuted boundary inputs remain outside a particular run’s evidence.

Back to CS.01
CS.02Show solution

Recheck the state under the lock

A wake can be spurious, or another consumer can acquire the lock first and remove the available item. Use a loop or predicate wait that resumes only when the queue is nonempty or a closed-state condition permits termination. Then handle closure and draining explicitly. Notification announces that something may have changed; it does not reserve an element for the awakened thread. The predicate must be inspected under the same synchronization protecting the queue state.

Back to CS.02
CS.03Show solution

A key identifies one logical payload

Return a conflict and do not apply another stock change. The key already identifies a committed operation with a stored payload and result. Changing quantity under the same key would make the retry’s meaning ambiguous: it could no longer be a safe repetition of the original operation. A genuinely new reservation needs a new key and is separately subject to stock and authorization rules. This preserves identity; it does not guarantee every new reservation succeeds.

Back to CS.03
CS.04Show solution

Selection can hide the worst outcomes

Failed requests may be disproportionately slow, so excluding them changes the population and can improve the percentile while user experience worsens. Report latency for all relevant completed attempts or logical requests under a defined timeout convention, together with failure and timeout rates. A separate successful-request latency distribution can be useful if labeled, but should not replace the full outcome picture. Keep workload and counting rules consistent between versions, especially when retries create multiple attempts per logical request.

Back to CS.04
CS.05Show solution

A valid representation can contain an unauthorized claim

JSON validation establishes a syntactic and structural input shape. It does not establish who the caller is or whether their asserted role is trustworthy. Authentication must establish identity, and authorization must consult trusted policy and resource ownership rather than accepting self-declared administration. TLS protects the connection and can authenticate endpoints under a configured trust model, but does not automatically make an application-supplied role authoritative. These layers solve different problems.

Back to CS.05
CS.06Show solution

Scope every claim to its evidence

An accurate report says that the documented tests passed on the specified Linux/compiler environment under the named sanitizers and that a specified single-threaded workload showed an observed speed ratio under stated timing boundaries and repetitions. Cross-platform validation requires actual builds and tests on additional platforms. Race-freedom requires a sound synchronization/ownership argument and appropriate analysis; stress or sanitizer evidence alone is not a universal proof, and address/undefined-behavior sanitizers are not ThreadSanitizer. A general 100-fold performance claim requires representative workloads, equivalent validated outputs, environment details, uncertainty, and integration costs. The bounded result may still be valuable when described honestly.

Back to CS.06

Retention and readiness#

Repair the specific boundary you could not explain: C09 arithmetic, C10 synchronization, C13 retry identity, C14 measurement, or C17 authorization. Advance toward specialization when you can review an unfamiliar design, identify its unproved assumptions, and propose a test or proof obligation that addresses them.