Skip to main content

Cumulative Review: Semesters 0, 1, and 2

Use 90–120 minutes for a first attempt, then compare with R1–R8 in the worked key. Mark each answer independent, assisted or needs repair; counts of “clear” answers do not override the competency gates. This review is practice before the exam and defense, included in the semester integration budget.

Interleaved tasks​

  1. R1 — programming + discrete maps: a catalogue contains IDs 4,7,4, and a job with value zero. Specify validation and exact lookup behavior. Explain why overwriting duplicates or equating zero with absence silently changes the task.
  2. R2 — logic + search: on [1,1,3,5], derive lower/upper bounds for 1 using half-open invariants. Name the decreasing quantity and empty-array result.
  3. R3 — induction + graphs: with durations 0:2,1:3,2:1,3:2 and edges 0→1,0→2,1→3,2→3, prove readiness values using topological induction. What changes after 3→0 is inserted? Include vertex-coverage checks.
  4. R4 — recursion + state: one eligible job [0,2) costs 0 and is worth 4; budget is zero. Show why it can be selected once, and explain how a mistaken unbounded recurrence could reuse it or fail to terminate.
  5. R5 — sets + interval semantics: compare [0,2) followed by [2,3) with closed intervals on those endpoints. Change predecessor search, proof and witness tests together. Identify which tests from the old contract no longer apply.
  6. R6 — mutation + persistence: a caller modifies a nested prerequisite list returned by lookup on an old version. Design an independent isolation check and account for copying or immutable sharing instead of assuming snapshots are free.
  7. R7 — probability + exactness: a historical key is absent from the current version used to rebuild a shared Bloom filter. Derive the failure and repair. Explain why a low observed false-positive rate does not address this defect.
  8. R8 — measurement + bit complexity: one timing favors DP over brute force, but the next request has very large binary-encoded B. Specify comparison controls, cost model, table admission rule and an honest over-limit response.

Repair record​

For each weak response, keep the mistaken assumption, a minimal counterexample, the repaired rule and one fresh test. Link it to S1–S6 and the relevant module assessment. Preserve real errors; do not invent a mistake to fill a template. Keep only useful retrieval prompts active while preparing for Semester 3.

Complexity and approximation evidence​

Recheck a reduction in both directions, distinguish a maximal from a maximum matching, and derive a cover bound from a matching certificate. Reuse the Module 6 delayed checks; explain why a weighted objective invalidates the unweighted guarantee.