a + b = K ?

• You are given a list of N non-negative integers. Your job is to find out if the list contains two integers a and b that add up to K. If yes, then output a and b.
• Design an efficient algorithm.
• N <= 10⁶
• K <= 10⁹

First Attempt: O(n²)

int a[N+1];

for i=1 to N-1 {
  for j=i+1 to N {
    if (a[i] + a[j] == K) {
      print(a[i]+ " and "+a[j]);
      return;
    }
  }
}
print("no such integers");

• Running Time: O(n²)
• Can you do better than this?

How about this algorithm?

int a[N+1];
boolean checked[K+1];

for i=0 to K { checked[i] = false; }
for i=1 to N {
  checked[a[i]] = true;
  if (checked[K-a[i]]==true) {
    print(a[i]+" and "+(K-a[i]));
    return;
  }
}
print("no such integers");

• Running Time: O(n+k)
• But is this really better?

Analysis

• If K is larger than N², then the second algorithm is worse.
• For a large K, the initialization phase takes a long time.
• The array checked[] might be too large for the memory available.
• Huge waste of memory: Most of the array checked[] will be empty.

Hashtables

• A memory-efficient alternative for sparse arrays.
• The set of posible keys (here: {0,1,2,...,K-1,K}) is called the universe.
• If the universe U is much larger than the number of keys actually stored (here: N), then a hashtable might be better than a standard array.
• In our problem we have |U| = 10⁹ and N <= 10⁶.

The basic idea

int hashtable[M];  // M > N

void store (int key, int value) {
  hashtable[h(key)] = value;
}

void get_value (int key) {
  return hashtable[h(key)];
}

int h (int key) {
  return h % M;
}

• Instead of using key as the index, we use h(key).
• h is a function that maps the universe U of possible keys to the indices of the hashtable.
• h : U -> {0,1,2,...,M-2,M-1}
• Usual hash functions:
  • h(k) = k mod "a prime not too close to a power of 2"
  • h(k) = floor(m*(k*c mod 1)) with 0<c<1 (Knuth suggests c = (sqrt(5)-1)/2 = 0.6180339887...)
• Problem: Collisions. Two keys might be mapped to the same index.

How likely are collisions?

• In a room with 35 people, how likely is it that two people have the same birthday?
• |U| = 365
• N = 35

Ways to resolve collisions

• Open Hashing
• Linear Probing
• Quadratic Probing
• Double Hashing

Open Hashing

• Each element of the hashtable is a linked list of elements that got mapped to this location.
• If you store N keys in a table of size M, the lists will have an average length of N/M.

Linear Probing

• If a cell is already in use, take the next one.
• hi(key) = h(key) + i
• Problem: Clustering