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

Good luck!

### Like this:

Like Loading...

*Related*

From the blackboard it looks like both e_i and d_i are in [0, 1/4]. Could you please confirm?

That should read 0 < e_i < 1/4 and 0 < d_i < 1/4.

Wednesday the 8th, I presume?

Yes.

For part 1, does it literally have to use an array? In particular, if the array runs out of space, do we need to account for the time spent copying data into a new, larger one?

Good point!

In general, on homework, quizzes , or exam, when it’s not clear what’s wanted, you should make reasonable assumptions and state them clearly. I will accept anything reasonable.

In the case of the bag heap problem, I hadn’t thought about what happens when you need to increase the size of the array. Now that you’ve drawn my attention to it, I like the problem even more, as it points out even in this simple situation, the importance of amortizedES analysis.

Thanks for bringing it to my attention! And YES, dealing with the doubling makes it an even nicer problem.

— manuel