Pre-Lab Due Tuesday, February 12th at 11:59 pm
Code and Post-Lab Writeup Due Friday, February 15th at 11:59 pm
We have studied the Binary Heap data structure in class. Now it is your turn to implement one. In support of both sorting and a future programming assignment about graph shortest paths, we will implement a min-first priority queue.
This lab consists of three components:
The pre-lab and post-lab are two separate assignments, due on different days. They should be prepared exactly as for Lab 1, following the guidelines in the eHomework Guide.
For purposes of the late policy, component 1 of the lab (the pre-lab) is a separate assignment from components 2 and 3 (code, writeup).
If the pre-lab is not turned in by its deadline, it will receive no credit even if the rest of the lab is on-time.
If the pre-lab is on-time, it will receive credit even if the rest of the lab is not turned in at all (or is late with no coupon).
Turning in the pre-lab late does not trigger a late coupon, either for itself or for the rest of the lab.
However, if a late coupon is consumed for the code/write-up, the deadline for the pre-lab will also move back one week, to three days before the new lab deadline.
The late policy for the code and writeup follows the rules for late labs given in the syllabus.
The pre-lab is intended to be completed before the coding component; it will help ensure that you understand the code and can work out an implementation strategy. For this reason, the pre-lab is due earlier than the other two components of the lab.
To succeed at the pre-lab, you need to read the provided code described below and be able to answer basic questions about its methods. These questions are given in the pre-lab document.
Prepare a brief PDF document that answers each of the questions asked in the pre-lab, following the eHomework guidelines. Submit your document to the "Lab 3 Pre-Lab" assignment via Gradescope by its due date.
We've provided you with some code to get started with your priority queue. Your job will be to fill in the missing methods using what you know about binary heaps.
In your repository, go to the heaps package in the labs source
folder. Do a Pull to make sure that you are looking at the latest
version of your repository.
There are three main source code files you need to consider, all in the
heaps package:
PriorityQueue.java contains the interface to the PriorityQueue ADT.
Decreaser.java implements the Decreaser class, which is a handle
to an object in the priority queue. You can access an object in the
queue via its Decreaser and decrease its value (which may cause it to
move in the heap).
MinHeap.java implements a min-first heap over objects of an
arbitrary comparable data type T. It implements the
PriorityQueue interface.
You will need to fill in some of the methods in the MinHeap class to
get your priority queue working. In particular, you'll have to
implement
decrease() to decrease the value of an object (accessed via its
Decreaser) and, if needed, move it to the right place in the heap;
insert() to insert a new object into the heap and return a new
Decreaser that references it;
extractMin() to remove and return the smallest object in the
heap;
heapify(), which is called as part of fixing up the heap after an
extraction.
Read the comments in MinHeap.java and Decreaser.java to better
understand what you need to implement. You can also take a video
tour of the provided
code,
courtesy of Dr. Ron Cytron.
In addition to correctly implementing these methods, you should add
calls to ticker.tick() to your code so that the number of ticks
counted by each heap operation is proportional to the number of
constant-time steps it performs.
We have provided you with three JUnit test files in the heaps.test
package to help you check that your heap is behaving as intended:
1) TestInsert : Tests the decrease() and insert() methods
2) TestExtractMin : Tests the heapify() and extractMin() methods
3) TestMinHeap: Tests all methods on small and large examples
It is highly recommended to implement your functions in the order given by these tests, fixing your code to be able to pass each unit test file before moving on to the next one. In addition to providing tangible checkpoints for your own convenience, following this strategy may allow you to earn partial credit for passing some unit tests even if your code does not pass them all.
As always, passing a unit test does not guarantee that your heap is correct -- you are ultimately responsible for correctness -- but failing it does indicate that there is a problem you need to fix.
For more testing advice, check out these videos from Dr. Cytron:
The unit tests check that the first element of your heap is stored at position 1, not 0, of the underlying array. They also check that, if the heap contains $n$ elements, every element of the array after the entries $1..n$ is null. Failure to implement these properties will cause your code to fail the unit tests.
Once your heap is working correctly, run the HeapTimer timing
experiment in the tests subdirectory. This experiment uses your
heap to sort an array of integers using the heapsort algorithm, which
inserts everything into a heap and then repeatedly extracts the
smallest element.
Running this experiment will produce time and ticks CSV files in your
repo's outputs folder. The tick counts will depend on where you've
inserted ticker.tick() calls in your code.
Remember to refresh your workspace to see the files in this folder as they are created.
Run the experiment to generate timing output, and use Excel to plot
the tick counts as you did in studio. If you've placed your tick()
calls correctly, the plot should reflect the $\Theta(n \log n)$
complexity of heapsort. (If you choose to plot the time data, it may
be noisy but should have roughly the same shape.)
Save your ticks plot in your output folder -- you'll be asked to
add it into your writeup. You won't be able to save the plot directly
in the CSV file, so instead take a snapshot: right-click
(control-click) on the plot and save it as a picture named heapticks
(.jpg or whatever) in your output folder.
To complete this portion of the lab, you must do the following:
Make sure your code passes the JUnit tests as we originally gave them to you. Our lab autograder script will use the output of these unit tests as part of the assessment of your code's correctness when grading.
Make sure you eliminate or disable any print statements or other
extraneous code, other than what is needed to implement the heap,
that you may have used for debugging. Extraneous code may slow
down your implementation to the point that our autograder will
fail it for taking too long to run.
Make sure you have placed ticker.tick() calls appropriately in
your solution. In particular, your solution's tick counts should be
consistent with your implementation's asymptotic complexity.
Make sure you do a Team/Pull on your repository before attempting to push your code. Remember, pull before push!
You must both commit and push all of your code to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
Please check that your code was pushed by logging into bitbucket.org, clicking on your repository, and viewing the source code to verify that it's the most up-to-date version.
Code that is not pushed to Bitbucket will not be graded, and you will not receive credit for it, even if your local copy is correct.
The post-lab writeup asks you to use your lab implementation to explore the performance of binary heaps and to reflect on what you've built.
Prepare a PDF document that answers each of the questions asked in the post-lab, following the eHomework guidelines. Submit your writeup via Gradescope by its due date.