Due: Wednesday, February 8th, 2012
1) Define a bag-heap to be an unsorted array of positive integers with a pointer to the minimum element. Compare the bag-heap to the Fibonacci heap on all operations supported by the Fibonacci heap.
2) Get tight bounds for the special case of a_i + b_j = c_k problem (3SUM) where:
for i = 0, 1, …, n-1:
a_i = i + e_i: 0 < e_i < 1/4
b_i = i + d_i: 0 < d_i < 1/4
c_i = n + g_i: 0 < g_i < 1/2