A difficult but interesting problem that some students might like.
Not for the exam.

Suppose you are given n points (numbers) in the unit interval, and you
want to determine the closest pair among them.  It seems that you
would need to sort them, scan them left to right and return the
closest.  This will require time O(nlog n).

However, using hash tables this can be done in expected time O(n) as
follows.  The randomization happens just in the first step.
The algorithm uses several hash tables as it progresses.  Each table
is characterized by a distance d, and has ceiling(1/d) slots.  Slot
i of the table represents the interval [id, (i+1)d].  Such a table
will be called a d-hash table.  When we say "insert x into T" we will
mean store x in the slot representing the interval containing x.


1.  Randomly order the numbers.  Resulting order: x1, x2, ... xn.
2.  Let d = |x1 - x2|
3.  Let T = d-hash table.
4.  For i=1..n
5.    Insert xi into T.  Say it goes into T[j].
6.    Let X = set of numbers in T[j-1],T[j],T[j]
7.    Find d' = smallest distance between xi and other points in X.
8.    If d'<d, then T = d'-hash table.  Insert x1..xi into T.  Set
d=d'
9.  end
10. Print d.

The correctness should be obvious.  At any time each table entry can
hold at most 2 points, and so in step 7 we will do at most O(1) work
in any iteration.  In step 8 of iteration i, we will do O(i) work if
d'<d, and so we need to prove that this does not happen too
frequently.

(a) First solve the following well known but apparently unrelated
problem.  Suppose n students arrive into a class in random order.  A
buzzer is sounded if the student arriving at any moment is the tallest
among the students in class so far.  What is the expected number of
times the buzzer will be sounded?  Hint: the probability of whether
the buzzer is sounded on step i does not change if I tell you who the
first i students are, as a group.

(b) Show using ideas similar to part (a) that the probability that
d'<d on step 8 in iteration i is O(1/i).  This will imply that the
expected work in step i is O(1) in every iteration.  Hence the total
work will be O(n) over all iterations.