Independent Assessment

Allow 90 minutes after practice. Close worked examples, code solutions, and keys; a calculator is allowed. Record assistance. Each item has4 points: model/assumptions1, derivation2, interpretation1. See rubric and consult solutions afterward.

1. AD1 — bounds: Prove 7n²+2n+1=Theta(n²) for n>=1 with explicit constants. Explain why 100 matching timings would not prove the result.
2. AD2 — recurrence: Solve T(1)=1,T(n)=2T(n/2)+1 exactly on powers of two. Count leaves, state a tight bound, and distinguish depth from total work.
3. AD3 — amortization: Empty array/capacity 1, doubling when full, cost one per copy/write. Derive total and maximum append cost for 9 appends; state a valid potential and why it bounds every prefix.
4. AD4 — proof: Specify and prove lower_bound for sorted integers with duplicates, using a half-open invariant and variant. Trace [0,3,3,7],target 3 and explain one nonterminating update bug.
5. AD5 — greedy and pruning: Give a count-optimal interval exchange argument, then refute its use for arbitrary weighted intervals with an explicit instance. Give a signed subset-sum example where overshoot pruning removes a solution.
6. AD6 — DP: For jobs (0,1,3),(1,3,3),(0,3,8),(3,4,2), derive a compatible-prefix recurrence, table, optimum value, witness, and time/space costs including reconstruction.
7. AD7 — evidence: Explain the unit-cost limitation in exact Fibonacci, the encoded-size limitation of O(nW) knapsack, and why a small brute-force oracle needs both its own checks and a separate proof for the optimized algorithm.

After 3–7 days, redo two weak competencies with changed numbers and a changed assumption, such as closed intervals, additive growth, or signed values. Use the rubric rather than treating a high total as permission to skip a missing foundational skill.