CSC 789 Assignment 3

Due date, October 7, 2004, 5:30 PM.

  1. Prove that in the CP algorithm, at any time, there are at most 4 input points in any cell of the current grid.
  2. 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).
  3. 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.
  4. 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