Skip to main content

Independent Dynamic Programming Assessment

Allow 3–4 hours for the initial written attempt, then separate implementation and remediation time within the module estimate. Close lesson examples and solution keys. You may use language documentation for syntax in the code phase; record external or AI help and complete a fresh explanation unaided afterward. Do not read scoring and solutions until saving an attempt.

Each task maps to one competency in the rubric. Give state, recurrence, boundaries, order, correctness argument, resource bound and requested witness. Arithmetic alone earns no mastery rating.

A1: state and counting contract​

For distinct unlimited denominations [1,2] and target 5, derive counters for unordered combinations and ordered sequences. Enumerate the counted objects or an equivalent complete classification and explain why each is counted once. Describe the exact-use zero base and a valid evaluation rank. Explain why memoizing an insufficient state cannot repair a missing constraint.

A2: sequence outputs​

Find a strict LIS for [4,1,2,2,3] with original indices, and align cab to abc under unit Levenshtein costs. Explain why upper-bound LIS search and an insert/delete-only alignment contract are different variants. Specify independent checks for both outputs and the full-table/fast-LIS costs.

A3: capacity and reconstruction​

Solve 0/1 knapsack for items [(2,5),(3,6),(4,8)], capacity 5. Reconstruct the chosen indices. Change to exact fill of weight 1 and explain new bases. Demonstrate the one-item ascending-update failure and the distinct descending capacity-pointer reconstruction failure. Account for storage in your repair.

A4: decomposing intervals and trees​

For dimensions [5,2,4,3], produce the optimal parenthesization and cost. For a star with center weight 7 and three leaves of weight 3, give independent-set states and a witness. Prove why the children can be optimized independently in each case. Explain why n-1 edges alone do not establish the tree precondition.

A5: subset tours and impossibility​

Solve the directed TSP matrix [[0,1,4],[3,0,2],[1,5,0]], then remove edge 2->0 and solve again. State the start base, closing rule, signed-cost behavior and absent-tour result. Give asymptotic state/transition bounds and an eight-byte rectangular state-payload estimate at n=20, excluding overhead.

A6: bounded counting​

Count integers with digit sum 2 in [0,205] and [100,205]. Define every state coordinate, next-tight update, terminal rule, zero policy and cache scope. Explain a "contains zero digit" variant's additional boundary-state requirement. Provide a finite enumeration check and a general resource bound.

A7: optimization contract and changed requirement​

Jobs (start,finish,value) are (0,2,4),(2,4,4),(0,4,9) with half-open intervals. Compare cardinality greedy to weighted prefix DP. Add costs 1,1,3 respectively and total budget 2. Derive the new state and give an optimal feasible schedule. Show exactly where the old state lacks required information.

A8: resource and verification review​

Review these claims and repair each: "n DP states imply O(n) time"; "two Fibonacci variables use O(1) bits"; "two-row edit distance also returns an alignment at no extra cost"; "a feasible witness proves its value is optimal"; "every DP is a single shortest path". Propose a tiny oracle and a changed-assumption test for an algorithm from A2–A7, explaining what finite tests cannot prove.