Skip to main content

Practice Solutions and Feedback

Attempt each lane first. Equivalent valid arguments and witnesses are accepted.

P01: State the problem​

Strict length 2, e.g. [1,3]; non-decreasing length 3, [2,2,3]. A canonical witness policy must state whether ties compare values or indices.

P02: Compare plans​

Greedy gives [4,1,1]; [3,3] refutes optimality. Exhaustive search certifies the bounded instance, and a last-coin recurrence supplies a general method.

P03: Audit a loop​

Below lo values are <t; at/above hi values are >=t. Both claims begin vacuously true and survive the appropriate comparison branch. hi-lo strictly decreases; at equality return lo. Membership needs the bounds guard.

P04: Look back​

Values 0,1,4,9 suggest n squared. Base n=0; add 2n+1 to n squared to obtain (n+1) squared. The identity counts unit squares in successive square borders; it does not generalise unchanged to arbitrary arithmetic progressions.

{0,1,2,3,4,6}. Reverse edges from 6 lead to 4 and 3; from 4 to 2; from 3 to 1; from 2 to 0 and 1. The self-loop at 0 does not add states. Include the target via a length-zero path.

P06: Test an analogy​

For n>=1: labelled 2**n-2; unlabelled half of that, since swapping nonempty labels has no fixed assignment. For n=0 both counts are 0; do not use the half formula outside its stated range.

P07: Disprove extrapolation​

n squared and n squared+(n-1)(n-2)(n-3) agree on 1,2,3 and give 16 versus 22 at 4. Finite observations permit many extensions.

P08: Choose informative cases​

Examples: ([],3)->0; ([1,2,2,4],2)->1; ([1,4],3)->1; ([2],1)->0; ([2],3)->1. Explain why duplicate tests discriminate lower-bound from arbitrary-match search.

P09: Necessary is not sufficient​

Parity does not rule out 7. With +4 or multiplication by 5, both moves preserve congruence 1 modulo 4, while 7 is 3 modulo 4. Alternatively enumerate reachable values <=7: 1 and 5. Both moves strictly increase positive states, so no larger state can return to 7.

P10: Construct and certify​

0 -> []; 3 -> None since neither 2a+5b=3 with nonnegative a,b nor a legal coin witness exists; 7 -> [2,5], optimal because no denomination is 7.

P11: Define sufficient state​

B(0)=0; B(a)=1+min B(a-c) over c<=a with reachable predecessor, otherwise infinity. Positive coins order dependencies by amount. Limited stock requires inventory or a denomination-index/stock-aware recurrence.

P12: A decreasing measure​

A descending sequence in nonnegative integers can take at most its initial value many strict decrements. Positive reals allow 1,1/2,1/4,... forever; bounded below does not imply a minimum step.

P13: Implement a boundary​

Return the first satisfying index, or length. The lab checker enumerates sorted small arrays and uses a linear predicate boundary as oracle. The proof still handles all valid sorted inputs.

P14: Implement construction​

Check sum, allowed coins and length separately. Breadth-first sum search reaches amounts in increasing coin counts and supplies an independent optimum for bounded targets. Do not accept a correct length paired with an invalid witness.

P15: Read before running​

The initial midpoint is 1 and ties do not replace it at index 0. It returns 1; the required first index is 0. A lower-bound search for 0 meets that contract on sorted input.

P16: Reduce a failure​

Failure is sum(values[:-1]) != sum(values), so it holds exactly when the final value is nonzero. A deletion-minimal result can be [2]. The reducer need not find a unique or globally smallest numerical value.

P17: Separate statuses​

found includes a validated path, including [start] when start=goal. unreachable requires complete exploration of the declared finite graph. unknown means the budget stopped exploration. invalid rejects missing vertices or malformed input.

P18: Specify time and identity​

State [now-24h,now), UTC, finite score, stable unique-ID tie rule and explicit rejection/reporting of duplicate IDs. The selected output can be shorter than input. Repeat calls with the same explicit now must agree.

P19: Timebox a handoff​

Grade the separation of observed data from hypotheses and the reproducibility of the two checks. A mismatch alone does not identify causation; safe next steps need ownership and reversibility information.

P20: Change an assumption​

For coins [3] and amount 6, unlimited [3,3] becomes invalid with stock one. Include remaining stock or an index that allows each denomination at most once. Bounded experiments cannot prove all instances correct.