
CSC 789 Assignment 3
Due date, October 7, 2004, 5:30 PM.
-
Prove that in the CP algorithm, at any time, there are
at most 4 input points in any cell of the current grid.
-
Let s1 ... sn be the set of input points after
random permutation in the CP algorithm.
Define Si = {s1 ... si}
for all i from 1 to n.
Denote by pi the probability that
the closest pair of Si+1 must contain
si+1. Show that pi <= 2/(i+1).
-
Explain how to implement a grid data structure where each lookup and
each insertion takes O(log n) time, where n is the maximum number
of items in the structure at any given time.
-
Suppose that H is a 2-universal family of hash functions M to N, where
M = {0, ... m-1} and N = {0, ... n-1}, as defined on page 220 of your
textbook. Suppose a member h of H is picked at uniformly at random,
and h used to hash a subset S of M to a table of size N. Let k be
the size of S. For a given item x in S, prove that the expected number
of other items of S which hash to the same position as x is less than k/n.
Assume that the members of S are unknown to us when we pick h, but that
the adversary does not know our choice of h when he picks S.

Back to
Course Page