Hashing

Question 1

(a) [3]

• Load factor $\alpha = n/m$. (1) — definition.
• Under simple uniform hashing each key is equally likely in any bucket, so expected keys per bucket $= n \cdot \tfrac{1}{m} = \alpha$. (2) — justification by symmetry/linearity.

(b) [6] For each other key $y \neq x$ define indicator $X_y = 1$ if $h(y)=h(x)$, else $0$. (2) By universality, $\mathbb{E}[X_y] = \Pr[h(y)=h(x)] \le 1/m$. (2) $C_x = \sum_{y\neq x} X_y$, so by linearity of expectation: $\mathbb{E}[C_x] = \sum_{y \neq x}\mathbb{E}[X_y] \le (n-1)\cdot\frac1m = \frac{n-1}{m}. \quad\text{(2)}$

(c) [4]

• Unsuccessful search hashes $x$ (cost $O(1)$) then scans the whole chain of its bucket. (1)
• Expected chain length $\le \alpha$ (or $\alpha$ for a probe key), so scan cost $O(\alpha)$; total $O(1+\alpha)$. (2)
• The "$+1$" accounts for computing the hash and accessing the bucket even when the chain is empty ($\alpha \to 0$); dropping it would wrongly imply zero cost when $\alpha=0$. (1)

(d) [4]

• $k=4$: $3\cdot4+5 = 17$; $17 \bmod 17 = 0$; $0 \bmod 6 = 0$. (1.5)
• $k=21$: $3\cdot21+5 = 68$; $68 \bmod 17 = 68 - 4\cdot17 = 0$; $0 \bmod 6 = 0$. (1.5)
• Both map to bucket $0$ → they collide. (1)

(e) [3]

• For any fixed deterministic hash function, an adversary who knows the function can choose $n$ keys that all hash to the same bucket, forcing $\Theta(n)$ worst-case per operation; randomizing the choice of $h$ from a universal family means no fixed input is bad in expectation, giving the probabilistic guarantee. (3)

Question 2

(a) Linear probing, $m=11$, $h(k)=k\bmod11$. [5]

Final: index0→22, 1→1, 2→13, 3→24, 4→12; others empty. (5) (deduct 1 per misplaced key)

(b) Double hashing, $h_2(k)=7-(k\bmod7)$. [5]

• 22: $h=0$ → slot 0.
• 1: $h=1$ → slot 1.
• 13: $h=2$ → slot 2.
• 24: $h=2$ occupied. $h_2(24)=7-(24\bmod7)=7-3=4$. probe $i=1$: $(2+4)\bmod11=6$ → slot 6.
• 12: $h=1$ occupied. $h_2(12)=7-(12\bmod7)=7-5=2$. probe $i=1$: $(1+2)\bmod11=3$ → slot 3.

Final: 0→22, 1→1, 2→13, 3→12, 6→24. (5)

(c) [4]

• In open addressing, a search stops when it hits an empty slot (that signals "key not present along this probe chain"). (1)
• If we simply empty a deleted slot, keys that were placed after it during probing become unreachable — the search terminates early at the false empty slot. (2)
• A tombstone marks "deleted but keep probing"; it is treated as occupied for search, free for insertion. (1)
• Concrete failure (from (a)): delete key 13 (slot 2) by emptying. Searching for 24: $h(24)=2$ finds slot 2 empty → wrongly reports 24 absent, though 24 sits at slot 3. (counts toward the 3 marks above)

(d) Aggregate/amortized proof. [6]

• Between resizes, each ordinary insertion costs $O(1)$; over $n$ inserts these contribute $O(n)$. (1)
• Resizes occur when size hits $1,2,4,8,\dots$; the $j$-th resize copies $2^j$ elements. (2)
• Total copy cost $\le \sum_{j=0}^{\lfloor\log_2 n\rfloor} 2^j = 2^{\lfloor\log_2 n\rfloor+1}-1 < 2n$ (geometric series). (2)
• Total cost $= O(n) + O(n) = O(n)$; dividing by $n$ gives amortized $O(1)$ per insertion. (1)

(e) [2] $\tfrac12\left(1 + \tfrac{1}{(1-0.9)^2}\right) = \tfrac12\left(1 + \tfrac{1}{0.01}\right) = \tfrac12(1+100) = 50.5.$ About 50 probes on average — catastrophic; hence linear-probing tables should resize at a much lower threshold (e.g. $\alpha \le 0.7$). (2)

Question 3

(a) [6]

def two_sum(A, T):
    seen = {}                     # value -> index
    for j, x in enumerate(A):
        if (T - x) in seen:       # O(1) avg lookup
            return (seen[T - x], j)
        seen[x] = j               # O(1) avg insert
    return None

• Single pass, each element does one lookup + one insert, both amortized $O(1)$ (hashing) → total $O(n)$ time. (4)
• Space $O(n)$ for the map. (2)

(b) Trace on $A=[3,8,2,5,11]$, $T=10$. [4]

Returned indices (1, 2) since $A[1]+A[2]=8+2=10$. (4)

(c) [6] Structures: a hash map key → node and a doubly linked list ordered by recency (head = most recent, tail = least recent). (2)

get(key):
    if key not in map: return -1
    node = map[key]
    move_to_head(node)      # unlink + insert at head, O(1)
    return node.value

put(key, value):
    if key in map:
        node = map[key]; node.value = value; move_to_head(node)
    else:
        node = new Node(key, value)
        map[key] = node; add_to_head(node)
        if len(map) > C:
            lru = tail.prev
            remove(lru); del map[lru.key]   # evict LRU

• Map gives $O(1)$ average lookup; DLL gives $O(1)$ unlink/insert/eviction because node pointers are known directly (no scan). (2 for pseudocode, 2 for the $O(1)$ justification)

(d) [2] A plain dict preserves order, but to mark a key most-recently-used you must move it to the end. Doing that naively (delete then reinsert) is $O(1)$ in CPython, but finding/removing the least-recently-used front element, or reordering an arbitrary middle element by rebuilding, would be $O(n)$; the explicit DLL (or OrderedDict.move_to_end) is needed to guarantee $O(1)$ eviction/repositioning. (2)

[
  {"claim":"h(4)=0 and h(21)=0 for a=3,b=5,p=17,m=6, so they collide",
   "code":"a,b,p,m=3,5,17,6\nh4=((a*4+b)%p)%m\nh21=((a*21+b)%p)%m\nresult=(h4==0 and h21==0 and h4==h21)"},
  {"claim":"Linear probing final placement: 22->0,1->1,13->2,24->3,12->4",
   "code":"m=11\ntab=[None]*m\nfor k in [22,1,13,24,12]:\n    i=0\n    while tab[(k%m+i)%m] is not None: i+=1\n    tab[(k%m+i)%m]=k\nresult=(tab[0]==22 and tab[1]==1 and tab[2]==13 and tab[3]==24 and tab[4]==12)"},
  {"claim":"Double hashing places 24 at slot 6 and 12 at slot 3",
   "code":"m=11\ntab=[None]*m\ndef h2(k): return 7-(k%7)\nfor k in [22,1,13,24,12]:\n    i=0\n    while tab[(k%m+i*h2(k))%m] is not None: i+=1\n    tab[(k%m+i*h2(k))%m]=k\nresult=(tab[6]==24 and tab[3]==12)"},
  {"claim":"Linear probing unsuccessful-search estimate at alpha=0.9 equals 50.5",
   "code":"al=Rational(9,10)\nval=Rational(1,2)*(1+1/(1-al)**2)\nresult=(val==Rational(101,2))"},
  {"claim":"Geometric sum of resize copies up to n=8 is < 2n",
   "code":"n=8\ntotal=sum(2**j for j in range(0,4))\nresult=(total==15 and total<2*n+1)"}
]