Hashing

Section A (1 mark each)

Q1 — (d) Reversible. Why: Hash functions need not be invertible; they map many keys to a small range, which is inherently many-to-one. Deterministic, uniform, and fast are the three core properties.

Q2 — (b) A linked list of entries. Why: Separate chaining resolves collisions by storing all colliding keys in a per-bucket list.

Q3 — (b) $\alpha = n/m$. Why: Load factor is items per slot; it measures how full the table is.

Q4 — (a) $(i+1)\bmod m$. Why: Linear probing steps one slot at a time (wrapping with mod).

Q5 — (b) To preserve probe sequences. Why: Physically emptying a slot would truncate a probe chain, making later keys unfindable; a tombstone keeps the chain traversable while marking the slot reusable.

Q6 — (c) $O(n)$ at resize. Why: Every existing element must be rehashed into the new table.

Q7 — (b) Occasional resize spread over many cheap inserts. Why: Doubling capacity makes the $O(n)$ resize occur rarely enough that the average per-insert cost is constant.

Q8 — (c) Step size from a second hash function. Why: Double hashing probes $(h_1(k)+i\cdot h_2(k))\bmod m$, reducing clustering.

Q9 — (b) Expected collisions bounded by randomizing the hash choice. Why: A hash function chosen randomly from a universal family bounds expected collisions for any fixed input, defeating adversarial worst cases.

Q10 — (b) Two-sum. Why: Store seen numbers in a hash set and check for target - x in $O(1)$ per element, giving $O(n)$ total.

Section B — Matching (1 mark each)

Q11 → B (quadratic probing formula) Q12 → A (chaining = linked list per bucket) Q13 → D (threshold triggering resize) Q14 → C (tombstone marks deletion) Q15 → E (LRU cache = hash map + ordering)

Section C — True/False + Justification (2 marks each)

Q16 — FALSE. (1 mark) Justification (1 mark): A hash function must be deterministic; the same key must always map to the same slot, otherwise items could never be found again. Speed alone is insufficient.

Q17 — TRUE. (1 mark) Justification (1 mark): As $\alpha \to 1$, few empty slots remain, so probe sequences lengthen dramatically; for linear probing the expected probes grow roughly like $\frac{1}{2}(1+\frac{1}{1-\alpha})$, blowing up near 1.

Q18 — FALSE. (1 mark) Justification (1 mark): CPython's dict uses open addressing (a probe sequence within a contiguous array), not separate chaining with linked lists.

Q19 — TRUE. (1 mark) Justification (1 mark): In chaining, buckets hold lists, so $n$ can exceed $m$ ($\alpha>1$). In open addressing each slot holds at most one item, so $n \le m$ and resizing is required before it fills.

Q20 — TRUE. (1 mark) Justification (1 mark): Iterate once, incrementing map[char] for each character; each update is amortized $O(1)$, giving one-pass $O(n)$ counting.

Marks Summary

• Section A: 10 marks
• Section B: 5 marks
• Section C: 15 marks (10 questions... 5 questions × 2 = 10) → Total = 25

(Note: Section C = 5×2 = 10 marks; A=10, B=5, C=10 → grand total 25. Adjust cover-page total to 25.)

[
  {"claim": "Load factor n/m with n=6 items, m=8 slots equals 0.75, the common resize threshold", "code": "n=6; m=8; alpha=Rational(n,m); result = (alpha == Rational(3,4))"},
  {"claim": "Linear probing expected probes for successful-ish estimate 0.5*(1+1/(1-alpha)) at alpha=0.75 exceeds probes at alpha=0.5", "code": "f=lambda a: Rational(1,2)*(1+1/(1-a)); result = f(Rational(3,4)) > f(Rational(1,2))"},
  {"claim": "Two-sum via hash set is O(n) which is asymptotically better than O(n log n) sort approach for large n", "code": "n=symbols('n', positive=True); result = simplify(limit(n/(n*log(n)), n, oo)) == 0"},
  {"claim": "Amortized doubling: total copy work for inserting N=1024 with doubling from 1 is < 2N", "code": "N=1024; total=sum(2**k for k in range(0,10)); result = total < 2*N"}
]