Skip to main content

Design Paradigm Practice

Allow 90–120 minutes. Fix the specification before choosing a paradigm. Use the separate solutions after an attempt.

  1. C1: For half-open jobs (0,2,2),(2,4,2),(0,4,9),(4,5,1), derive maximum count and maximum value. Give the greedy exchange proof's preserved quantity.
  2. C2: Sort these jobs by(end,start,index), derive compatible prefixes, fill weighted DP, and reconstruct original indices. Explain why copying witnesses into every cell risks quadratic work.
  3. C3: Coins are unlimited positive integers3 and4; target 5. Give the minimum-coin recurrence, base case, impossible-state value, and answer. Contrast target 6 with largest-coin-first greedy.
  4. C4: Implement that recurrence with memoization and tabulation on small targets0..20. Explain cache keys, dependency order, and recursion-depth limits. Prove equality of the mathematical recurrences, then compare outputs; checking21 values alone is not the proof.
  5. C5: Enumerate subsets of n jobs as an oracle. Account for constructing and checking each subset instead of calling the entire implementation Theta(2^n) automatically. State what agreement on n<=8 can and cannot establish.

Extend C1 by changing intervals to closed endpoints, so touching jobs conflict. Identify which comparison changes and re-derive the result. Do not keep a half-open proof for the new semantics.