Independent Problem-Solving Assessment

Allow 2–3 hours for a first attempt; this is an estimate, not a speed gate. Close solution pages and record permitted notes or tools. Explain reasoning, not just answers. Finish before opening the key.

A01

An API must “return the best route.” State six missing contract decisions, including multiple valid outputs, invalid input and budget exhaustion. Give examples distinguishing no path from unknown.

A02

Coins are 1,4,5 and the target is 8. Write a greedy hypothesis, refute or justify it on this instance, and give a sound replacement strategy.

A03

Prove the lower-bound loop from lesson 3 terminates and returns the first index with value >=t. Trace [1,3,3,7] with t=3 and the empty input.

A04

For graph {a:[b], b:[c], c:[b], d:[]}, enumerate vertices reaching c. Explain how reverse traversal handles the cycle and the zero-length path.

A05

Someone infers f(n)=2**n from values at n=0,1,2. Give a different matching formula and state what would establish the claimed general rule.

A06

Starting at 2, legal moves add 4 or multiply by 3. Decide whether 7 is reachable, with an initialisation and preservation argument. Explain why an even target would require more work.

A07

For unlimited coins 3,5 and target 8, derive the recurrence, return a minimum witness and justify optimality. Address targets 0 and 1.

A08

A reducer stops at length 3 because every one-element deletion passes; the failure predicate is “length is 1 or 3.” Is this globally shortest? Explain the actual guarantee and a smaller failing input.

A09

A routine allows each coin denomination only once, but memoises solely by remaining amount while exploring arbitrary choices. Explain the lost information and design a sufficient state with a termination argument.

A10

You have 20 minutes to investigate a wrong aggregate. After 15 minutes you have a reproducible mismatch and a recent-deploy correlation, but no causal test. Write the handoff, next discriminating check, and one claim you cannot yet support.