CSE 373 Data Structures Sp08, Homework 3

Electronic Turn-in of code and write-up due: 11:59pm Thursday, 5/01/08.
Printouts of code and report due at the beginning of class on Friday, 5/02/08.

Programming:

Implement three priority queues according to the PriorityQueue interface provided.  You should provide the following implementations:

 

Each heap implementation should be in its own file (BinaryHeap.java, ThreeHeap.java, MyHeap.java).  Implement the BinaryHeap as discussed in lecture.  For the ThreeHeap we suggest starting with a copy of your BinaryHeap code and making changes as necessary.  For your third heap implementation, feel free to get creative.  The simplest possible implementation might just use an array (sorted or unsorted), a linked list (sorted or unsorted) or a tree.  Whatever you do, be sure it implements the PriorityQueue interface provided, and does not use parts of the Java collections framework.  Your priority queues only need to work with doubles.

Your implementations should automatically grow (if interested you may also make them shrink - this is optional) as necessary.  Note: Growing an array implementation one element at a time is not likely to be the most time efficient solution, and you should NOT use Java class libraries (no import statements).

 

Provided code:

We will be testing the code that you submit - so we will expect that you have done the same!  (We will also be asking you to turn in your testing code.)

Write-up Questions:

This week your write-up involves a comparison of your three heap implementations.  I would expect these reports to be a couple of pages long, potentially longer if you include many graphs or tables.  Exceptional reports may be awarded a small amount of extra credit, so have fun with this!  Please prepare a report that addresses the following:

  1. Big-O Analysis: What is the worst case big-O running time of isEmpty, insert, findMin, and deletemin operations on all three of your heap implementations (Binary Min Heap, ThreeHeap, MyHeap).
  2. Timing your code: Perform several timing experiments (similar to what you did in homework #2, where you timed pieces of code), to examine the running time of all three of your heap implementations.  An experiment will include running the same client code (that uses a Priority Queue) for your three different heap implementations *for several values of N* and timing this.  It is up to you to write and to determine what this client code should be.  Just be sure that it exercises your insert and deletemin operations “in a reasonable manner” – reasonable here means eventually deleting everything that has been inserted into the heap.  You are not required to explicitly measure calls to findMin and isEmpty but feel free to do so if interested.  Similar to homework #2, graphing your results is recommended, but a table of results will work also.
  3. Comparison: Compare what you see in your experiments, to what you expected to see based on a big-O analysis.  (This is similar to what you should have done in homework #2 as well.)  In your discussion you should answer these questions:
    1. How useful was big-O for predicting the measured run time of insert and deletemin for your three implementations?  
    2. If your predictions based on Big-O differed substantially from your measured times, speculate as to why this occurred.
    3. Which of your three implementations would you recommend to someone who needs to use a heap?  Why is that one preferred?  Are there any conditions under which you might suggest using your other implementations?
  4. Testing: Please briefly discuss how you went about testing your three heap implementations.  Feel free to refer to your submitted test files.

 

What to turn in:

 

Electronic Turn-in should include the following files:

 

In addition, you should print out all of the above and turn it in at the beginning of class on Friday, May 2, 2008.

 

Have fun with this!