Foundations to FrontierPart IX: The graduate coreBezhig

GD: Graduate-readiness diagnostic and repair map

12 exercises, each with a complete solution.

Do not treat advanced placement as a judgment about all your abilities. Attempt short unaided solutions; mark a topic not yet studied instead of guessing. This diagnostic locates a prerequisite, not a numerical “mastery score.” The twelve tasks retain the identifiers of the earlier graduate checkpoint.

GD.01FSolution

Trace s=0; i=0; while i<3: s=s+i*i; i=i+1. Give (i,s)(i,s) at each loop head, the final sum, and the history represented by the accumulator.

GD.02FSolution

A contract says that for a sorted nonempty input list a function returns its minimum. Does an incorrect result on an unsorted list violate that promise? State what extra requirement would make rejection of unsorted inputs necessary.

GD.03CSolution

Evaluate let x=2 in (let x=x+1 in x)+x under lexical scope. Distinguish the inner initializer, inner body, and final outer occurrence.

GD.04CSolution

An algorithm performs nn iterations, copying nn elements each time. Another uses nlog⁡2nn\log_2 n comparisons and allocates a large buffer. Give the first work bound and explain why comparison counts alone do not establish which runs faster at n=16n=16.

GD.05CSolution

A detector catches 90% of positives and falsely flags 5% of negatives. Positives are 1% of cases. Find the probability of a true positive given a flag, under these population probabilities.

GD.06CSolution

For A=(101112)A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix} and b=(1,2,2)Tb=(1,2,2)^T, explain the request Ax≈bAx\approx b. Is exact equality possible?

GD.07CSolution

A fixed workload spends 20% of time in an unchanged serial part. Under ideal scaling of everything else, compute speedup with eight workers and the limiting speedup. State what the model ignores.

GD.08CSolution

Two workers each read counter value 4 and then each writes its read value plus one. Give the final value in this interleaving and the intended value. Explain why an aligned integer does not establish an atomic increment or valid C++ concurrent behavior.

GD.09TSolution

A server commits a request but the reply is lost. A client times out. Does the client know the request committed, know it did not, or have an uncertain outcome? Specify a safe retry identity rule.

GD.10TSolution

A scaler is fitted to the full dataset before a random row train/test split, with several rows per person. Identify two leakage risks and give a corrected order.

GD.11CSolution

For L(w)=(2w−3)2/2L(w)=(2w-3)^2/2, derive L′(w)L'(w) and one gradient step from w=0w=0 at rate .1.1. Explain what the derivative measures.

GD.12TSolution

A new implementation runs once in 9 ms and the old once in 10 ms. State what follows, what does not, and an experiment that would strengthen the performance claim.

Placement before solutions#

GD.01–03 errors suggest C01/C04/C15 before G01–G02. GD.04 suggests C06–C08 before G03. GD.05–06 suggest A01–A04 before G04–G05. GD.07–09 suggest C09–C13 before G06–G08. GD.10–11 suggest A04, the chain rule, and T03 before G12–G15. GD.12 suggests C14 and G16. Separate an arithmetic slip from inability to state the denominator, invariant, domain, or comparison being used.

Complete solutions: GD#

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

GD.01Show solution

The loop head describes processed values

Loop-head states are (0,0),(1,0),(2,1),(3,5)(0,0),(1,0),(2,1),(3,5). Each body adds the square of the old index, then increments the index. At every head s=∑k=0i−1k2s=\sum_{k=0}^{i-1}k^2. The final guard is false at i=3i=3 and the result is 5. Summing through ii in the invariant would include a value not processed yet.

Back to GD.01
GD.02Show solution

A precondition is not a validation promise

No. The stated promise is conditional on sorted nonempty inputs. It says nothing about other inputs. A separate requirement to reject every unsorted list with a specified error would make a failure to reject a violation. A public API may deliberately choose that stronger contract; do not silently infer it from a conditional postcondition.

Back to GD.02
GD.03Show solution

Shadowing is local

The outer xx is 2. The inner initializer is evaluated in that environment, producing 3. The inner body sees 3, while the final occurrence again sees the outer 2. The result is 3+2=53+2=5. Reusing one mutable binding without restoring scope can incorrectly return 6.

Back to GD.03
GD.04Show solution

Count every implemented operation

The first performs n2n^2 element copies, hence Θ(n2)\Theta(n^2) under a constant-size element-cost model. At 16, allocation, locality, constants, element costs, and compiler choices may dominate. The comparison count of the second does not count all its work. Require identical outputs and workload, then measure repeated runs with the timing boundary stated.

Back to GD.04
GD.05Show solution

The conditioning event defines the denominator

Among 10,000 representative cases, expect 100 positives and 9,900 negatives. Expected true flags are 90 and false flags 495. Thus P(+∣flag)=90/(90+495)=2/13≈.1538P(+\mid\mathrm{flag})=90/(90+495)=2/13\approx.1538. Sensitivity .9.9 is P(flag∣+)P(\mathrm{flag}\mid+), not the reversed probability. Prevalence matters even with unchanged detector rates.

Back to GD.05
GD.06Show solution

An inconsistent system suggests projection

Writing x=(a,c)Tx=(a,c)^T, the equations demand a=1a=1, a+c=2a+c=2, and a+2c=2a+2c=2. The first two give c=1c=1 and contradict the third. Least squares asks for the column-space prediction closest to bb, not exact equality by magic. G05 derives (a,c)=(7/6,1/2)(a,c)=(7/6,1/2) and verifies residual orthogonality.

Back to GD.06
GD.07Show solution

The unchanged fraction imposes a ceiling

Normalize old time to 1. New ideal time is .2+.8/8=.3.2+.8/8=.3, so speedup is 10/3≈3.3310/3\approx3.33. As worker count grows the limit is 1/.2=51/.2=5. The model excludes overhead, contention, communication, imbalance, and changed workload; it is not a measured hardware guarantee.

Back to GD.07
GD.08Show solution

A compound update is not one atomic operation

Both modeled writes are 5, giving 5 rather than the intended 6. Atomic individual accesses would not make the read-modify-write sequence indivisible. In C++, conflicting unsynchronized non-atomic accesses can be a data race with undefined behavior, so the interleaving is an explanatory model rather than a promise that unsafe C++ must return exactly 5. Use a valid atomic read-modify-write or protect the full update, with appropriate lifetime and ordering rules.

Back to GD.08
GD.09Show solution

Timeout leaves an uncertain remote effect

The client has an unknown outcome. A timeout cannot distinguish a lost request from a committed request with a lost reply. Retry with the same stable identifier and payload; the server must store the identity and result consistently with the effect, return the prior result on a matching retry, and reject conflicting reuse. Eventual success still needs progress/availability assumptions. An ID alone does not create the transactional protocol.

Back to GD.09
GD.10Show solution

Split on the deployment unit before fitting transforms

The fitted transform uses held-out distribution information, and repeated people may cross splits, making evaluation of new-person behavior misleading. Split by person and relevant time before learning preprocessing. Fit the scaler only on training data and reuse it unchanged on validation/test. Keep validation choices separate from the final untouched test assessment. Matching this split to the intended deployment question is more important than choosing a fashionable percentage.

Back to GD.10
GD.11Show solution

A derivative is sensitivity of the loss to its parameter

Chain rule gives L′(w)=2(2w−3)=4w−6L'(w)=2(2w-3)=4w-6. At zero it is −6-6, so wnew=0−.1(−6)=.6w_{\rm new}=0-.1(-6)=.6. Original loss is 9/2=4.59/2=4.5 and new loss is (−1.8)2/2=1.62(-1.8)^2/2=1.62. The sign predicts a local decrease for a suitable positive step; it does not prove every learning rate converges. The derivative is a scalar rate of change in loss per parameter change, not the loss value itself.

Back to GD.11
GD.12Show solution

One pair is an observation, not a stable conclusion

Those executions differed by 1 ms under whatever conditions were used. They do not establish typical speed, statistical reliability, cause, or a universal 10% improvement. Check identical results, fix workload and build settings, define what setup is included, alternate order across repeated pairs, preserve raw samples, and report variation and limitations. Avoid choosing the best single run after trying many settings and presenting it as a prespecified comparison.

Back to GD.12