Homework 3 Clarifications

• Here are some comments on when you have timed your implementations and are trying to make sense of what you see. For hw #2, the code we were timing was fairly straightforward, we were just measuring a number of math operations (sum++), and we were measuring some very big differences - O(N) vs. O(N^4) for example. This made it very obvious that for large N you really would prefer the O(N) algorithm. Some of you saw how your machine seemed to "hang" when you used large values of N for the N^4 and N^5 algorithms. It was not hanging, just taking a really really really long time!!!! :)

  The timing for hw 3 is a bit different. We are measuring operations on data structures that may have certain big-O running times, but if we actually counted the number of instructions, some of those constants (that big-O analysis throws out) might actually have a big impact - particularly for small values of N.

  You are likely to see timing values that are very similar for your binary heap and your three heap. Depending on what you do for your 3rd heap, you may also see similar values there. This is fine. Note that we are not asking or expecting that the experiments you devise will end up with graphs that match your expected big-O curve exactly - it is fine if they do not. If you are getting widely varying timings - you can try several runs and then averaging the values you get back for the same implementation.

  The point is to have successfully done timings for all of your implementations and to think (and write) a bit about why you think you might be seeing what you see. I am definitely not expecting you to calculate c values or really to do any detailed calculations based on your timing data. But I do expect you to address the questions in the assignment and hopefully you can find *something* that you expected in your timing data - one implementation is faster/slower than another consistently (discuss why? only on certain data sets?), one *operation* is consistently faster/slower between two implementations, etc.

• Duplicate values *are allowed* - your heap implementations must handle this situation by allowing 2 or more copies of the same value to exist in the heap simultaneously. For example when you call deletemin and you have say {3, 3, 6, 7} in the heap, it would just return one of the 3's, then on the next deletemin it would return the other 3. It does not matter which 3 is returned first. This corresponds to a "tie" in priority - like two print jobs of the same size. According to our definition of priority queue, the only thing that must be guaranteed is that all the 3's will be reuturned before a 6 or 7 would be returned, and that the 6 would be returned before the 7.