DP Foundations and State Design Lab

Budget 5–7 focused hours across P1–P5. For each task preserve a first attempt, state/proof, one counterexample or boundary case, and a corrected explanation. Use separate feedback only after committing your reasoning.

P1: a state collision

In the graph s->a,a->u,s->b,b->u,u->a,a->t, compare the two paths to u. Explain why endpoint-only longest-simple-path state is insufficient, propose a sufficient repair and bound its states. Explain why a DAG changes the argument.

P2: states are not transitions

Count distinct subproblems and candidate transitions for rod cutting through length n, and intervals/splits for a chain of n matrices. Compute both transition totals at n=4. Contrast these with the number of calls in merge sort on n=8 distinct positional elements. Do not equate total merge work with call count.

P3: cache contract

A memoized function for digit sum closes over N and S. Is caching tight=true states valid? What if the same cache survives changing N? Propose a safe lifetime. Separately explain why a denomination 1 undermines a "sparse remainder" claim for top-down exact coin count.

P4: correct value, invalid reconstruction

Trace descending one-array 0/1 updates and capacity-only parent pointers for one item (2,3), capacity 4. Show the value and the invalid reconstructed selection. Repair it and give the revised memory bound. State why merely reversing the loop is not a repair for this contract.

P5: numeric cost

Prove the two-value Fibonacci invariant. Give arithmetic-operation, integer-object, live-bit and total bit-work bounds under linear-time addition. Explain why a constant number of variables does not promise feasibility at n=10^9.