computer science homework

CPS 350: Assignment 4 Due 11:55 pm, 3/27/2017 (100 pts)

This is NOT a team project. No late submission will be accepted.

Receive 5 bonus points if turn in the complete work without errors at least one day before deadline.

Receive an F for this course if any academic dishonesty occurs

1. Purpose The purpose of this assignment is to implement priority queues.

2. Description

2.1. Implementation (30 points for BinaryHeap.java, 45 for ThreeHeap.java)

Your main task is to implement two priority queues. All two implementations should implement

the provided PriorityQueue interface (include implements PriorityQueue in your Java code),

which means they should work with priorities that have type double and there are no

corresponding items attached to the priorities. Your implementations should be as follows:

• A class BinaryHeap that implements a binary min-heap as we discussed in class, using

an array to store the conceptual complete tree.

• A class ThreeHeap that implements a min-heap where each non-leaf node has 3 children.

You should still use a contiguous portion of an array to store the conceptual complete

tree. We suggest you make a copy of your BinaryHeap class and make changes as

necessary.

Put your two implementations in two separate Java files, BinaryHeap.java and ThreeHeap.java.

Your priority queues should allow duplicates. That is, two or more copies of the same value

should be allowed to exist in the heap at the same time. For example, if you call deleteMin and

you have {3.0, 3.0, 6.0, 7.0} in the heap, it would just return one of the 3.0 values, then on the

next deleteMin it would return the other 3.0. It does not matter "which" 3.0 is returned first.

According to our definition of priority queue, what must be guaranteed is that both 3.0 values

will be returned before a 6.0 or 7.0 is returned, and that the 6.0 would be returned before the 7.0.

Your implementations should automatically grow as necessary. (If interested, you may also have

them shrink when appropriate; this is optional.) For any arrays, you should start with a small

array (say, 10 elements) and resize to use an array twice as large whenever the array becomes

full, copying over the elements in the smaller array. Do the copying with a for loop rather than

any Java library methods (even though using the library is how one would normally do it). You

may use the length field of an array as needed.

Be sure to test your solutions thoroughly and to turn in your testing code. For instance, you

may generate 1000 random numbers, insert them into a priority queue, and keep deleteMin() as

long as the priority queue is not empty. Part of the grading will involve thorough testing

including any difficult cases. For this assignment, we will be grading more strictly for things like

style and efficiency.

2.2. Questions (25 points)

The questions include comparing the actual run-time of your implementations. We would expect

the reports to be at least a couple of pages long, quite possibly longer to have room for relevant

graphs or tables.

Submit a report.pdf file, answering the questions in this template report.docx file:

1. (5pts) What is the worst case asymptotic running time of isEmpty, size, insert, findMin,

and deleteMin operations on all your heap implementations? For this analysis you should

ignore the cost of growing the array. That is, assume that you have enough space when

you are inserting a value.

2. (5pts) Which of your two 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?

3. (5pts) Briefly discuss how you went about testing your two heap implementations. Feel

free to refer to your testing files, which you should submit.

4. (10pts) You implemented a binary-heap and a three-heap. Now think if you can

implement a four-heap, a five-heap, etc.

a. In a short table, indicate for a binary heap, a three-heap, a four-heap and a five-

heap, where the children for the node at array index i are. For example, the first

row of the table would indicate that for a binary heap, the two children would be

at i*2 and i*2+1.

b. For a d-heap where d is a variable representing the number of children (like two,

three, four, five, ...), give an arithmetic formula for calculating where the left-

most child for the node at array index i are. For example, a wrong answer in the

right format would be i*d+14. Naturally, your formula should produce the right

answer for all the rows in your table from part (a).

2.3. Bonus Components (10 points)

The following suggestion is meant for you to try if you finish the requirements early.

1. (5pts) Implement a d-heap where d is the number of children for non-leaf nodes. Your

class should implement the same priority queue interface and it should use a contiguous

array portion as in your first two implementations. It should include an empty

constructor and additional constructor that takes d as an argument, work correctly for

any d greater than or equal to 2, and use d as the number of children for nodes.

2. (5pts) Implement a binary heap that works for any type (not just doubles). It should use

Java generic types to allow any priority type that implements an appropriate interface for

comparing two priorities and your heap should allow items of a second generic type that

are "attached" to each priority. That is, each node contains a key-value pair, where key is

the priority. Note this implementation will not implement the provided interface, so

provide any additional comments necessary to explain how your class should be used.

3. Grading notes If your program does not compile, you receive zero points for that program. Additional

deductions:

1. (5 points) Your code does not follow the style guide discussed in class/textbook.

2. (30 points) Your code does not have author name, date, purpose of this program,

comments on the variables and methods, etc.

4. Turn in

You should ZIP the following files and submit the ZIP to isidore.

• BinaryHeap.java

• ThreeHeap.java

• Any additional Java files needed, if any.

• The Java files you used to test your implementations.

• The Java files you used to time your implementations.

• report.pdf, containing answers to Questions in 2.2.

• Any additional files for the bonus credits in a zip file named extracredit.zip. Please make

sure that this zip file decompresses its contents into a folder called extracredit

and not into a bunch of individual files.

Do not turn in PriorityQueue.java and EmptyPQException.java. You must not change these files.

Your implementations must work with the code as provided to you.