1. Progressively bad hash functions
Recall that for any prime p≥m, the family of hash functions hab:M→N given by hab(x) = ((ax + b) mod p) mod n for a∈ℤp*, b∈ℤp is 2-universal: ∀x≠y Pr[hab(x) = hab(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 Sn such that Pr[hab(Sn) 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 dG(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 dH(f(u),f(v)) ≥ dG(u,v) for all u,v∈V(G), let the expected distortion δ(P) = maxu,v∈V(G) E[dH(f(u),f(v))/dG(u,v)].
Let G = Cn be a cycle with n vertices. Show that there exists a probability distribution P on (f,H) such that H is always Pn-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?