CSE 373 Data Structures 10au, Homework 3 (68 points)

Electronic Turn-in due: 11:45pm Thursday, 10/28/10.

Programming (41 points):

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 (a binary min heap) as discussed in lecture.  For the ThreeHeap we suggest starting with a copy of your BinaryHeap code and making changes as necessary.  Your ThreeHeap should still follow the contiguous structure (complete tree) form of the binary min heap discussed in class. 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.)

Grading: each data structure is worth 11 points, which is 33 points total. Insert(): 4 points, DeleteMin(): 4 points, and isEmpty + makeEmpty(): 3 points. Any mistakes elsewhere like in the  constructor() could lead to a points reduction too if it makes these functions not work well. There are another 8 points for style such as poor comments, inefficient design, didn't follow directions (including all code) etc. For this assignment we will be grading more strictly for things like style and efficiency than we did on HW #1.

 

Write-up Questions (27 points):

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 (8 points): 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 (12 points) : 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 (5 points): 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. (3 points for a and b) If your predictions based on Big-O differed substantially from your measured times, speculate as to why this occurred.
    3. (2 ponits) 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 (2 points) : 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:

 

Above and Beyond:

There are no explicit above and beyond options for this assignment, but exceptional reports may receive small amounts of extra credit.  You might also consider implementing several different heaps from very simple to very complex (the book discusses Leftist, Skew, Binomial Queues, and Fibonacci).  If you implement other heaps and discuss them in your report, please include the Java code for those heaps as well.  The file named MyHeap.java is the one that will be graded as part of the original assignment.