Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 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?

2014-06-17 11:58