Sequence and Grid DP Workshop

Budget 7–10 hours across P6–P10. Derive before implementing; compare values with small exhaustive enumeration and inspect witnesses independently. Feedback is in Practice Solutions.

P6: strictness and reconstruction

Compute strict LIS and longest nondecreasing subsequence for [2,2,1,3]. Give original indices, both search predicates, and a proof sketch for tails dominance. Explain why [2,4,6] is not a valid witness for [3,5,6,2,4].

P7: edit semantics

Fill the entire table for ab -> acb, return alignment columns and verify the ungapped strings. Compare unit substitutions against insert/delete-only edits on a -> b. Explain what must change for affine gap penalties; implementation of that extension is optional.

P8: which knapsack?

Use items [(2,3),(3,4)], W=4. Compute the ratio-first greedy result, exact 0/1 optimum and unbounded optimum. Then solve exact-fill weight 1. Give bases, loop direction and reconstruction strategy for each variant you implement.

P9: counting objects rather than tables

With distinct denominations [1,2], count unordered combinations and ordered sequences totaling 4. Derive both recurrences, explain the loop nesting difference, and justify count[0]=1. What happens if duplicate denomination records are silently treated as different types? Use the coin-counting worked example first if this distinction is unfamiliar.

P10: unreachable and negative

Count right/down paths in a 3-by-3 grid with center blocked. Then find a maximum-reward path in [[-5,-2],[-3,-4]] counting both endpoints. Report the output when the destination is blocked. Explain why adding four-direction moves invalidates the same fill-order proof.