# 1. Progressively bad hash functions

Recall that for any prime p≥m, the family of hash functions h_{ab}:M→N given by h_{ab}(x) = ((ax + b) mod p) mod n for a∈ℤ_{p}^{*}, b∈ℤ_{p} is 2-universal: ∀x≠y Pr[h_{ab}(x) = h_{ab}(y)] ≤ 1/n. Show that it is *not* k-universal for any constant k>2, by showing that for any fixed k and sufficiently large n there exists a set S_{n} such that Pr[h_{ab}(S_{n}) is constant] = Ω(1/n) (with a constant that may depend on k).

# 2. Low expected distortion

Given a graph G, let V(G) be the set of vertices in G and let d_{G}(u,v) be the length of the shortest path from u to v in G, where u,v∈V(G).

Given a graph G and a probability distribution P on pairs (f,H) where H is a graph and f:V(G)→V(H) such that d_{H}(f(u),f(v)) ≥ d_{G}(u,v) for all u,v∈V(G), let the **expected distortion** δ(P) = max_{u,v∈V(G)} E[d_{H}(f(u),f(v))/d_{G}(u,v)].

Let G = C_{n} be a cycle with n vertices. Show that there exists a probability distribution P on (f,H) such that H is always P_{n-1}, the path with n vertices, and δ(P) = O(1).

# 3. Defective skip lists

Suppose we are given a skip list with a head node and n nodes with parameter p (the probability that a node at level k also appears at level k+1), and that we choose one of the non-head nodes uniformly at random and remove it without updating any pointers, so that any search that attempts to access the removed node fails.

What is the expected number of nodes that are still reachable by a standard skip list search starting from the head node?