Assessment Solutions and Scoring

Open after submitting an attempt. Award the model point only when assumptions match the problem; unsupported correct numbers receive at most calculation points.

1. AD1: For n>=1, 7n² <= 7n²+2n+1 <= 10n²; constants7,10 and threshold1 establish Theta. Timing observations are finite and depend on a machine/model, unlike this quantified inequality.
2. AD2: A full binary tree with n unit leaves has n-1 internal nodes costing1 each. T=2n-1, Theta(n), while depth is log2(n). Substitution and T(1)=1 also verify it.
3. AD3: Copies1+2+4+8=15; writes9,total 24,max9. Final capacity 16, Phi=2*9-16+1=3; 3*9-Phi=24. Initial Phi=0 and nonnegativity on all append-only states support every prefix. Charge3 is amortized, not a cap on each append.
4. AD4: The outside regions satisfy values below lo<target and values at/above hi>=target. Sortedness supports lo=mid+1 or hi=mid; hi-lo decreases. Trace intervals[0,4),[0,2),[0,1),[1,1) gives index 1. Using lo=mid can repeat forever on a singleton whose value is too small.
5. AD5: Replacing an optimum's first interval with an earliest-finishing interval preserves count and leaves later intervals feasible. (0,1,1),(1,2,1),(0,2,5) disproves weighted optimality: greedy weight2 versus5. Target3, partial5,remaining[-2] disproves signed overshoot pruning. The derivation points require both counterexamples and the exchange reasoning, not merely the word greedy.
6. AD6: Sort indices 0,2,1,3; compatible prefixes0,0,1,3. D=[0,3,8,8,10], recurrence max(skip,take+best_compatible_prefix), base0. Witness indices 2,3 has value 10. Sorting and binary predecessor search O(n log n), table and recovery O(n), storage O(n), under unit-cost arithmetic. The witness must be feasible and use original indices.
7. AD7: Exact Fibonacci values have growing bit size; two integer slots do not mean constant bits or constant-cost addition. Binary-encoded W has Theta(log W) bits, making O(nW) pseudo-polynomial. Oracle agreement tests only the chosen finite domain and can share a bug with the candidate. Specify tests and proof obligations separately; account for setup/output in proposed benchmarks.

Scoring: model1, substantive derivation2, requested interpretation1 per item. A reviewer may split the two derivation points across the subparts, but must apply that split consistently. A critical model error blocks the associated competency even when arithmetic is correct.