Hashing

Q1 (12 marks)

(a) $h(k)=k\bmod 11$. Insert order $22,8,33,44,19,30$:

• $22 \to 0$ (empty) → index 0
• $8 \to 8$ (empty) → index 8
• $33 \to 0$ (occupied by 22) → probe 1 → index 1
• $44 \to 0$ (occ), 1 (occ 33) → probe 2 → index 2
• $19 \to 8$ (occ), 9 (empty) → index 9
• $30 \to 8$(occ),9(occ),10 (empty) → index 10

Final table: (6 marks — 1 per correct placement)

(b) Delete $33$ at index 1 → replace with tombstone (DEL marker). (2)

Search for $44$: $h(44)=0$.

• probe index 0 → key 22 ≠ 44, continue
• probe index 1 → tombstone, must continue (do NOT stop)
• probe index 2 → key 44 found. ✓

Probe indices: 0, 1, 2. (2)

Why tombstone (2): If we simply blanked slot 1, the search for $44$ would hit an empty slot at index 1 and conclude $44$ is absent — but $44$ lives at index 2 because it was placed there by probing past the old key $33$. The tombstone preserves the probe chain: it tells search "keep going," while telling insert "you may reuse this slot."

Q2 (10 marks)

(a) $h_1(100)=100\bmod 13$. $13\cdot7=91$, $100-91=9$ → start at 9. $h_2(100)=1+(100\bmod 11)$. $11\cdot9=99$, $100-99=1$ → step $=1+1=2$.

Probe sequence: $(9 + 2i)\bmod 13$:

• $i=0$: 9 → occupied
• $i=1$: 11 → empty → insert at 11

Wait — check: slot 9 occupied (given), slot 11 empty → inserted at 11.

Probe indices computed: 9, 11. Since 11 is empty, insertion stops. (Full sequence would be 9, 11, 0, 2, 4, 6, 8, 10, 12, 1, 3, 5, 7.)

Marks: correct $h_1=9$ (2), correct $h_2=2$ (3), correct final placement at 11 (2).

(b) (3) $h_2$ must never be $0$ because a step size of $0$ makes the probe sequence stay on the same slot forever — an infinite loop that never explores the table. Choosing $m$ prime ensures $\gcd(\text{step}, m)=1$ for every allowed step, so the probe sequence $(h_1 + i\cdot h_2)\bmod m$ visits all $m$ slots before repeating — guaranteeing an empty slot is found if one exists.

Q3 (12 marks)

(a) Policy: after insertion, if $\alpha = n/C > 0.75$, double $C$. Threshold at $C=4$ is $3$ (since $3/4=0.75$ ok, $4/4>0.75$). So resize triggers when count exceeds $\lfloor 0.75C\rfloor$.

• After 1st insert: $1/4=0.25$ → $C=4$
• After 3rd insert: $3/4=0.75$ (not $>$) → $C=4$
• After 4th insert: $4/4=1.0>0.75$ → double → $C=8$
• After 7th insert: $7/8=0.875>0.75$ → double → $C=16$
• After 13th insert: $13/16=0.8125>0.75$ → double → $C=32$

Answers: 4, 4, 8, 16, 32. (1 each)

(b) (7) Ordinary insertions each cost $O(1)$: $n$ insertions cost $O(n)$ total. Resizes occur when the table doubles: at capacities $4,8,16,\dots$ A resize at capacity $C$ rehashes $\approx C$ elements (cost $\Theta(C)$). The capacities at which resizes happen form a geometric sequence up to the final capacity $\le 2n$. Total rehashing work: $\sum_{j} C_j \le 4 + 8 + 16 + \dots + 2n \le 2\cdot(2n) = 4n = O(n).$ Explicitly, $\sum_{i=0}^{k} 4\cdot 2^i = 4(2^{k+1}-1) < 8\cdot 2^{k}$, and the largest term $\le 2n$, so the sum $< 4\cdot(2n)=O(n)$. Total work $= O(n)\text{(inserts)} + O(n)\text{(rehashing)} = O(n)$. Amortized per insertion $= O(n)/n = O(1)$. ∎

Marks: inserts O(n) (1), resize cost Θ(C) (2), geometric sum bounded by O(n) (3), conclude amortized O(1) (1).

Q4 (8 marks)

(a) (2) $\mathcal{H}$ is universal if for all distinct $x\neq y \in U$: $\Pr_{h\in\mathcal H}[h(x)=h(y)] \le \frac{1}{m}.$

(b) (6) Fix key $x$. Define indicator $X_y = 1$ if $h(y)=h(x)$, for each of the other $n-1$ keys $y\neq x$. Then $X=\sum_{y\neq x} X_y$. By universality $\mathbb{E}[X_y]=\Pr[h(y)=h(x)] \le 1/m$. (2) By linearity of expectation: $\mathbb{E}[X] = \sum_{y\neq x}\mathbb{E}[X_y] \le \frac{n-1}{m}.$ (2) With $m=n$: $\mathbb{E}[X] \le \frac{n-1}{n} < 1.$ (1) Expected search time for $x$ = time to scan its bucket $= O(1 + \mathbb{E}[X]) = O(1)$. (1) ∎

Q5 (8 marks)

(a) (5) Use a hash set of seen values plus a result set of pairs.

found = set()          # values seen so far
pairs = set()          # canonical (min,max) tuples
for x in array:
    need = T - x
    if need in found:
        pairs.add( (min(x,need), max(x,need)) )
    found.add(x)
return pairs

• Avoiding duplicate pairs (2): store each pair in canonical order (min,max) in a set, so (2,5) and (5,2) collapse and repeated occurrences don't re-add.
• Avoiding element reuse when $T=2a$ (2): because we only test need in found before adding the current x, a value $a$ pairs with another $a$ only if a previous $a$ was already inserted — i.e. two distinct array positions exist. A lone $a$ with $need=a$ won't match itself. (1 for clean pseudocode)

(b) (3) Average time $O(n)$ (each lookup/insert $O(1)$ expected). Worst case $O(n^2)$ — occurs only when hashing degrades so that essentially all keys collide into one bucket (adversarial keys / bad hash function), making each set operation $O(n)$. With a good/universal hash and random data this is negligible.

[
  {"claim":"Q1: linear probing final placements for 22,8,33,44,19,30 mod 11",
   "code":"m=11\nkeys=[22,8,33,44,19,30]\ntab=[None]*m\nfor k in keys:\n    i=k%m\n    while tab[i] is not None:\n        i=(i+1)%m\n    tab[i]=k\nresult = tab==[22,33,44,None,None,None,None,None,8,19,30]"},
  {"claim":"Q2: double hashing 100 into m=13 with slots 9,3 occupied lands at 11",
   "code":"m=13\nocc={9,3}\nh1=100%13\nstep=1+(100%11)\ni=0\nwhile ((h1+i*step)%m) in occ:\n    i+=1\nslot=(h1+i*step)%m\nresult = (h1==9 and step==2 and slot==11)"},
  {"claim":"Q3: capacities after inserts 1,3,4,7,13 with double-when->0.75 policy",
   "code":"def caps(n):\n    C=4;cnt=0;out={}\n    for _ in range(n):\n        cnt+=1\n        if cnt/C>0.75:\n            C*=2\n        out[cnt]=C\n    return out\nd=caps(13)\nresult = (d[1]==4 and d[3]==4 and d[4]==8 and d[7]==16 and d[13]==32)"},
  {"claim":"Q3: total rehash cost 4+8+16+...+2n is O(n); sum < 8n for n up to 1000",
   "code":"import math\nok=True\nfor n in range(4,1001):\n    total=0;C=4\n    while C<2*n:\n        total+=C\n        C*=2\n    ok = ok and (total < 8*n)\nresult = ok"},
  {"claim":"Q4: universal hashing expected collisions with m=n is < 1",
   "code":"n=symbols('n',positive=True)\nexpected=(n-1)/n\nresult = simplify(expected<1)==True or bool((expected.subs(n,1000))<1)"}
]