Skip to main content

Semester 2: Algorithms: Answer Key and Solution Outlines

Open after preserving an attempt. Equivalent correct proofs, topological orders and tied optimal witnesses are accepted. Points describe the exam; the rubric controls competency decisions. Award partial credit for a sound independent method with a repairable arithmetic slip, and record conceptual errors separately. Do not equate copied model answers with independent evidence.

E1 / S1: counts and input size — 15 points​

At n=8 the inner counts are [1,2,2,3,3,3,3,4], total 21. Generally the count is the sum of floor(log2(i))+1 for i=1..n. The upper bound is n times the largest summand; the last half of the i values each contribute logarithmic work, giving Θ(n log(n+1)). 5 points: count 2, upper/lower reasoning 3.

For n=2^h, level l has total nonrecursive work n(h-l), l=0..h-1. There are n leaves of cost 1. Thus T(n)=n*(1+h*(h+1)/2), or Θ(n log²n) as n grows. Include the base case separately. 5 points: levels 2, sum/bound 2, leaves/base 1.

B occupies Θ(log(B+1)) binary bits, while the table ranges over its numeric magnitude. O(mB) is pseudopolynomial, not generally polynomial in that encoded length. State fixed-word bounds or account for arbitrary-precision operations; huge values also affect addition/comparison costs. 5 points: encoding 3, arithmetic/model qualification 2.

E2 / S2: ordering and contracts — 15 points​

Stable result: [(1,B),(2,D),(3,A),(3,C)]; lower_bound(3)=2 and upper_bound(3)=4. For lower bound, indices below lo have keys less than target; indices at or above hi have keys at least target; candidate interval is [lo,hi). Upper bound substitutes “at most”/“greater than.” Each update reduces hi-lo. On equal merge keys take the left record, preserving original order by induction. 8 points: result/bounds 3, invariant/termination 3, stability argument 2.

A balanced ordered map supports deterministic logarithmic path operations under bounded comparison cost; reporting k range items costs at least Ω(k), typically O(log n+k) with appropriate traversal. Repeated insertion builds in O(n log n). Hash-map expectations depend on hashing, collisions, load and resizing policy; a full traversal/sort may be needed for ordered output. Construction and rehash cost cannot disappear into a universal constant lookup claim. 7 points: ordered operations/output 3, hash assumptions 2, setup and justified choice 2.

E3 / S3: readiness certificate — 15 points​

Valid order [0,1,2,3] or [0,2,1,3]. Finishes: {0:2,1:5,2:3,3:7}. For each v, finish is duration(v) plus max predecessor finish, with empty maximum zero. Check unique complete vertex coverage, every edge forward, and the recurrence at every vertex; a loose feasible finish alone does not establish earliest finish. 8 points: order 2, times 3, full certificate 3.

BFS levels [0,1,1,2] count hops, not weighted preparation durations or maximum predecessor finish. Adding 3→0 creates cycle 0→1→3→0 (or via 2); reject the input rather than return a partial schedule. With adjacency lists, processing/checking costs O(V+E), including isolated nodes. 7 points: BFS distinction 2, cycle/rejection 3, cost/coverage 2.

E4 / S4: state and witness — 25 points​

Job 15 is excluded: start 6 is before required finish 7. Stable eligible finish order is [10,11,13,12,14]. Compatible-prefix counts in that order are [0,1,0,3,3]. In particular, finish 6 is compatible with start 6. 5 points: eligibility 2, stable order 1, predecessors 2.

D(i,b) optimizes the first i jobs within budget b. Base D(0,b)=0. Compare skip D(i-1,b) with value(i)+D(p(i),b-cost(i)) when cost fits; otherwise skip. Evaluate increasing prefixes with all budget columns. Any valid optimum either excludes i, or includes it and has all remaining jobs in its compatible prefix with remaining budget. Replacing that remainder by a better feasible prefix solution would improve the optimum, proving sufficiency. Positive interval length ensures p(i) is strictly smaller; zero cost does not break termination. 8 points: state/base 2, recurrence/order 3, exhaustive proof 3.

Final values for budgets 0..5: [0,0,8,10,14,18]. Budget 5 chooses [13,14], cost 5, value 18. Recover by following skip/include decisions with the matching prefix and budget; validate distinct IDs, eligibility, compatibility, cost and summed value. Earliest-finish greedy takes 10 and 11 (cost 4, value 11) and cannot afford another positive-cost job, missing 18. 7 points: row 2, valid witness/recovery 3, greedy counterexample 2.

Use the empty solution rather than forcing negative-value jobs. Filtering/sorting and predecessor searches precede O((m+1)(B+1)) table work/cells; witness work is O(m), and bit costs/encoded-budget limits remain explicit. Arbitrary selection dependencies may demand a discarded job outside the compatible prefix; the state does not remember enough. 5 points: zero/negative handling 1, resource model 2, changed-assumption failure 2.

E5 / S5: amortization and isolation — 20 points​

Actual append costs [1,2,3,1,5] total 12; potentials [1,2,2,4,2] from initial zero; charges [2,3,3,3,3] total 14. Actual total equals charges plus initial potential minus final potential: 14+0-2=12. A resizing append is still linear in the old size. 5 points: ledger 3, telescoping and per-call distinction 2.

Version 0: [13,14], value 18, cost 5. Version 1 without 13: [11,14], value 14, cost 4. Version 2 without 14, forked from 0: [13,12], value 16, cost 5. Starting version 2 from version 1 instead would lose 13 and yield value 12 using [11,12]. Recheck old reports/lookups after every fork and mutate returned nested data to test isolation. Zero-valued records remain present. 5 points: version results 3, independent isolation tests and presence semantics 2.

Version 1 omits job 13, which exists in version 0. A shared filter built only from version 1 can return negative for a real version-0 key. Build from the union of supported versions or use a suitable per-version filter; confirm all positives in the exact requested catalogue. Shared bits cannot safely be cleared as if each key owned them. 5 points: concrete false-negative mechanism 3, safe coverage/confirmation 2.

Copied snapshots require time/storage proportional to their graph/catalogue/reference data, and retained versions accumulate that storage. Reference lookup scans the catalogue; planning recomputes the DP. A logarithmic persistent point-sum update does not recompute interval compatibility or the scheduling optimum. 5 points: honest snapshot/lookup costs 3, separating the scheduling state 2.

E6 / S6: evidence and pruning — 10 points​

Each height event has probability 2^-20; union bound gives at most 1024/2^20=1/1024. This controls a height event under the stated random model, not a complete search-time tail or a guarantee against an adaptive observer. 4 points: bound 2, assumptions/limits 2.

Record input sizes/shapes, equivalent outputs, setup/allocation/output inclusion, runtime/hardware, warmup, repeated samples and spread. Use bounded brute force only where it terminates. An observation does not quantify over all large inputs. 3 points: comparable measurements 2, claim boundary 1.

A branch with current value 0 can still add a legal value-10 job; incumbent 5 does not justify pruning it. For maximization, a valid upper bound on every completion of that branch at most the incumbent permits pruning when any optimum suffices. A heuristic score or beam width alone is not such a bound; preserving all tied optima can require a different equality rule. 3 points: counterexample 1, valid bound 1, exact-versus-heuristic distinction 1.

Project and checkpoint calibration​

The reference kit demonstrates one valid baseline: topological readiness, stable finish order, predecessor search, a full DP table and copied snapshots. Accept different implementations if the contracts/proofs hold. Black-box tests do not establish stable-sort implementation, complexity or independent authorship; inspect source and ask the learner to adapt a fresh case.

The checkpoint's six prompts map directly to S1–S6. Accept an accurate resource ledger, order/search invariant, graph certificate, state/witness proof, isolation trace and evidence-boundary defense respectively. Reject a polished packet with one missing competency. A fixed public fixture is practice, not an unseen assessment.

Cumulative review R1–R8: feedback​

  • R1: map input IDs to records and validate uniqueness before work; distinguish missing from zero. A lookup used to detect duplicates must not silently overwrite.
  • R2: [1,1,3,5] has lower_bound(1)=0, upper_bound(1)=2; invariants concern whole excluded prefixes/suffixes. Both bounds return 0 on an empty array. Strict interval shrink establishes termination.
  • R3: graph finishes are 2,5,3,7 as in E3; induction follows topological order. A directed cycle is not repaired by ignoring its last edge.
  • R4: a single job [0,2), cost 0, value 4 with B=0 is selectable once, yielding 4. Prefix decreases on inclusion; an unbounded recurrence could reuse it incorrectly or recurse forever.
  • R5: [0,2) and [2,3) can coexist; closed intervals sharing 2 cannot. Closed intervals require finish < start instead of finish <= start. Change predecessor comparison and witness tests together; do not change only prose.
  • R6: copy/reference aliasing can corrupt old versions and returned records. Mutate a nested returned prerequisite list, then re-read every affected version. No change should appear; account for copying or immutable sharing.
  • R7: rebuild shared filter coverage from every supported version; use exact confirmation for positives. A missed old key creates a false negative regardless of how small the measured false-positive rate appears.
  • R8: include identical input generation/setup policies, check equal answers, repeat samples and separate model counts from time. O(mB) may be huge when B has a short binary representation. Decline an over-limit exact request explicitly.

These answers are calibration, not learner-pilot evidence. Record reviewer disagreement and actual time in the rubric review record.