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!


6 thoughts on “HW3

  1. 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s