Reason it out.
Write it for marks.

Two things are being graded: the bound and the one-line reason. “Unsorted ⇒ nothing rules out any element ⇒ must compare against each in the worst case.” Name n (|S|). Don't write more — 2 points, two sentences maximum.

Each bound + its 4-to-8-word reason. The hash-table line is the trap: the question explicitly asks for both expected and worst case — leaving out O(n) costs the point. If asked what makes the expected case hold: a good hash function spreads keys uniformly, load factor kept constant by resizing.

The examiner wants you to separate the model (O-notation counts comparisons) from the machine (a random disk access costs ~10⁵× a RAM access). Naming either B-trees or the Bloom filter as mitigation shows you see where the problem is heading — (e) asks for the Bloom filter explicitly.

“Naive” means: translate the mathematical definition literally, base case first. n < 3 covers exactly n ∈ {0, 1, 2}. Nothing else is wanted here — memoization comes later in the problem, and writing it now answers the wrong subpart.

“Derive” = show the recurrence and the tree argument, not just say “exponential”. The three-line chain (recurrence → bound by the 3-ary tree → node count × constant work) is exactly the supported reasoning the cover sheet demands. The true growth rate is the tribonacci constant ≈ 1.84ⁿ; O(3ⁿ) as an upper bound with the tree argument is the expected full-marks answer.

“Complete” means every call node, including the three base-case leaves under deg(3). Adding the returned values (deg(3)=3, so deg(4)=5) is the free sanity check that shows the tree is right. Note deg(2) appears twice — that duplicated subtree is precisely the argument for part (d)'s memoization.

Top-down = keep the recursive shape, add a cache. “Without auxiliary tools” bans lru_cache — a hand-rolled dict is exactly what's wanted. The memo=None default avoids Python's mutable-default-argument trap (a shared dict across calls) — mentioning that shows real understanding. Always end a DP answer with the new complexity: that's where the 8 points close.

Bottom-up variant (asked in 2020–21): a=b=c=1, loop for _ in range(3, n+1): a, b, c = b, c, a+b+c, return c — O(n) time, O(1) space.

Name the tool, one sentence on what it does, then the naive code with the decorator on top — that is the whole answer. (Your old handwritten sheet had exactly this import line at the top. It stays.)

This is your handwritten sheet's binary-search block, verbatim — it survives to the new sheet. The space question is the actual test: recursion isn't free, each nested call holds a frame until it returns, and binary search nests Θ(log n) deep. The iterative rewrite eliminates exactly that. Say “auxiliary space” — the input itself doesn't count.

Bisection is binary search on a continuous function: the invariant is sign(f(a)) ≠ sign(f(b)), so the interval always contains a root (intermediate value theorem — name it if asked for justification). The loop keeps the invariant by replacing the boundary whose sign matches the midpoint's. The hints in the question are a grading checklist: (1) they want the sign-preserving update shown, (2) they want your tolerance convention stated in words — either |f(m)| < tol or interval width (b−a)/2 < tol is accepted if you say which. The bound check at the top plus max_iterations as a fail-safe are the remaining marks.

“Rethink the signature” is the hint that pure min_max2(data) can't recurse cleanly — add an index (or slice, but slicing copies O(n) per level, worth a remark). Pattern: solve the rest recursively, combine with the current element. Both return a tuple — matching “returns both” in the statement.

The one condition line carries the whole function: take from S1 when S2 is exhausted (j == len(S2)) or S1's front element is smaller (guarded by i < len(S1) so we never overrun). i + j is both the write position and the loop bound — the invariant is “S[0 : i+j] holds the i+j smallest elements, merged”. This is the course's own implementation (it was on your handwritten sheet, with the same short-circuit trick) — reproduce it exactly; inventing a different merge risks losing the “as discussed in class” marks.

(b): split into four quarters, sort each recursively, then merge pairwise — the statement says you may reuse two-list merge, so three merge calls (S1+S2, S3+S4, then the halves) is the intended shape. T1, T2 = S1+S2, S3+S4 just creates containers of the right length for merge to overwrite.

(c): the derivation must name the recurrence, then the theorem with the applicability check — the cover sheet's “fundamental theorem” rule. Per level all merges touch each element a constant number of times → O(n) per level; depth log₄n; log₄n = log₂n / 2 — a constant factor, so identical asymptotics. That sentence is (d)'s answer too: no asymptotic benefit (possibly fewer recursion levels, but more merge passes per level — constants shuffle, Θ(n log n) stays).

Both halves are required: the bound with the decision-tree sentence, and the escape hatch (“yes, if we don't only compare”). Naming one non-comparison sort with its complexity and its assumption (keys from a bounded/integer universe) completes it.

“Names only” questions are pure sheet lookups — this is why the sorting table belongs on your A4 side. For the explanation: definition in one sentence + a two-element tie example + one “why it matters” clause. Done in four lines.

The swapped flag is the entire trick: a pass with zero swaps proves sortedness, so bail out. State both the new best case and that the worst case is unchanged — the comparison is what the subpart is really asking for.

Grading checklist for any list-mutation method: (1) the odd case — the statement explicitly demands “handle it correctly”, and raising a clear error is correct handling; (2) the empty list (size 0 is even — the new node becomes the head); (3) walk exactly size/2 − 1 hops so cur is the node before the middle; (4) link the new node before re-pointing cur — the classic order mistake loses the tail; (5) update _size. Five checkpoints ≈ 9 points.

(b) is four lines, but two of them are the graded ones: the empty-list guard and the size decrement. The removed node needs no explicit freeing — Python's GC collects it once unreferenced (say this if asked). (c) wants two benefits each — symmetric answers; complexity-flavored phrasing (O(1) head ops vs O(1) indexing) is the safest currency.

The usage snippet (for value in lst:) tells you the method name: Python's for-loop protocol calls __iter__. Any function containing yield is a generator — Python builds the iterator object for you, state (the paused position) included. Yield the element, not the node. This same 5-liner answered the 2023 Summer exam too — it recycles.

Four graded moves: normalize the negative index (k += n — the explicit requirement); grow when full (doubling, matching the class design — this is why append is O(1) amortized); shift from the back so nothing is overwritten; write + increment size. If the variant asks for __setitem__ instead (2023–24 resit): same negative-index normalization, then bounds-check and assign — no shifting.

“k-tuple” is a prompt to count what the graph has: nodes and edges always (V, E); weights add w: E→ℝ; the graph is directed, so E contains ordered pairs and A need not be symmetric (here it isn't: A[1][2]=3 but A[2][1]=2 — different arcs). Read each arrowhead carefully: the two arcs of a node pair are separate directed edges with separate weights. State your row-convention (“row = from”) — either convention is accepted if declared.

The question names its own rubric: use O and Θ. Θ(n) for pop(0) is the precise claim (it always shifts, not just in the worst case); O(1) for the deque ops. Then say why a queue is the right ADT: breadth-first order = first discovered, first expanded. In (c), reference the line numbers explicitly (“rewriting lines 07 and 09”) — the statement demands it — and change nothing else; append on line 18 already works on a deque.

Symmetry is a statement about two subtrees mirroring each other, so the recursion needs a two-argument helper: outer-vs-outer (left.left vs right.right) and inner-vs-inner. The two base cases carry points: both empty → symmetric; exactly one empty → not. This is verbatim from your old handwritten sheet — it was right then and it answered a real exam since. For the marking subpart (a): a tree is symmetric iff this mirror test passes; single-child nodes break symmetry unless mirrored on the other side.

The universal tree-recursion template: my value + recurse into whichever children exist. The is not None guards are the graded detail — calling None.sum() crashes. O(n) time (each node once), O(h) stack. The same skeleton answers count, height (1 + max(...)), find-max — one template, many exam questions. (Also on your old sheet — kept.)

“Write out intermediate steps” = the rubric: H(S), then per attribute the split counts, the weighted remainder, the gain. The layout above (one line per attribute) is the fastest complete form. This instance contains a deliberate tie — air and wind produce identical splits ((4+,1−)/(0,1−)); saying “tie — either is a valid root” is the mark-winning observation, silently picking one without comment is not. Calculator: log₂x = ln x ÷ ln 2; store H-values you reuse (0.811 = H(3,1), 0.722 = H(4,1), 1 = H(1,1)) — they recur constantly.

“Full tree” = repeat the root procedure inside every impure branch. The efficient exam order: (1) root gains, (2) close the pure branches immediately (cloudy, rainy are all-negative — no calculation needed, say “pure → leaf”), (3) recurse only into sunny with its 3 rows. Attributes with one value in the subset (air = all warm) have gain 0 — one clause, no arithmetic. Again a tie (humid/wind) — state it. Verify at the end: run each training row down the tree; all 6 must classify correctly.

obj[k] = v syntax → the dunder __setitem__; that name is half the marks. The other half: handle both verbs in “add or update” — scan for the key first, only append when absent. O(n) per operation is fine here; that's the point of the unsorted table (the hash table in (b) is the fix).

Pure calculator work: 3i+2, then the mod-11 remainder — write the h(i) line per key (that's the “supported” part), then the bucket table with chains in insertion order. Collisions here: buckets 2, 4, 9 each chain two keys. Every value machine-verified. The nested-dict two-pointer: plain dict needs the inner dict created first; defaultdict(dict) does it automatically.

The (e) description has a fixed skeleton the examiner looks for: structure (bits + k hashes), the two operations, the asymmetry (FP yes / FN no), the complexity, and the application sentence tying it to the story. The MC options are recycled across years with the same four claims — memorize which is the false one: FP depends on m (the fuller the filter, the more false positives).

The guided derivation only wants the limit identity (1−1/n)ⁿ ≈ e⁻¹ applied to the exponent the question already arranged for you. The numeric instance is the full pipeline: k* formula → round to integer (the statement demands it — 3.33 → 3; checking k=3 vs k=4 both is the safe move, k=3 gives ε≈10.0%, k=4 ≈10.1%, so 3 wins) → plug into the FP formula with your integer k, not 3.33. All numbers machine-verified. Keep 3+ digits through the calculation, round at the end.

(c) is bound + justification in one line — the n² × n sentence is the “supported” part. (d): block matrices multiply exactly like 2×2 numbers, just with matrix blocks — row-times-column at block level. 8 block multiplications of half size; that's the setup Strassen improves on (8 → 7).

Substitute the given M-definitions, expand (distributivity holds for matrices), cancel the ±A22·B11 pair, and land on the block formula from (d) — then say that's what it had to equal. Four lines, no cleverness. Note: the M₁…M₇ definitions and the Cᵢⱼ recombination are always printed in the exam — never memorize them; only the expansion technique and the target (the (d) formulas) matter. The exam has asked C1,1 and C2,1 in different years — same three moves.

The cover-sheet rule bites precisely here: “if you use a fundamental theorem you must indicate this and explain why it applies.” So the full-marks skeleton is: name (Master theorem) → parameters (a=7 subproblems, b=2 size divisor, d=2 from the additions) → applicability → case comparison (log₂7 > d) → result → interpretation (asymptotically faster than n³). Same chain answers merge sort (a=2,b=2,d=1 → n log n) and binary search (a=1,b=2,d=0 → log n) — one memorized procedure, three recurring exams questions.

Three graded atoms: what α/β are (amplitudes, with the |·|²-gives-probability link), the bit-vs-qubit difference (superposition + collapse on measurement), and the normalization constraint. Your old handwritten sheet had exactly |α|²+|β|²=1 — kept. If gates appear (older exams): X = [[0,1],[1,0]] flips amplitudes (NOT); Hadamard H = (1/√2)[[1,1],[1,−1]] maps |0⟩ to (|0⟩+|1⟩)/√2 — an equal superposition.

Both follow the same 3-sentence template the question dictates: what problem + one mechanism phrase + speedup in O notation with the classical comparison. The classification pair to keep straight: Grover = quadratic (search), Shor = exponential (factoring). In the 2025 Summer context question (“how could a quantum computer do the lookup?”) the answer is Grover applied to the unsorted username set: O(√n) instead of O(n).