Assignment 11
Learn to implement a priority queue and heapsort algorithm.
Explore the time compexity of sorting algorithms.
Instructions
The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.
Make sure you follow the style guidelines for code indentation.
You will submit this assignment by the deadline using the Web-CAT submission system.
With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.
On top of every file you submit you will have the names of both partners, and the pair number.
The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.
Submission Details:
Make sure every file with name Xyyy.java contains as the first class or interface the definition of class Xyyy or interface Xyyy.
Make sure that the classes with tests are named Examples... as appropriate.
Your report on the findings of the sorting detective should be written as a professionally prepared report - use a word processor create tables of data, charts that illustrate your results, and clearly written descrioption of your findings.
Submit this report as one file in one of the following formats: pdf, MS Word, or open office word processor.
Due Date: Wednesday, April 3rd, 11:00 pm.
Problem 1: Priority Queue and HeapSort
Your job is to design a priority queue using the heap algorithm. You then use this to implement the heapsort algorithm and add it to a collection of algorithms to be evaluated for time-complexity.
The descrioption of this assignment is written in a tutorial style - so you can recall the lecture details.
A heap is a complete binary tree. It means that every level is filled, except for the last level. The last level is filled from the left.
So a heap with five nodes will have the following shape:
node-1
/ \
node-2 node-3
/ \
node-4 node-5
The nodes are labeled by levels from left to right, starting at 1.
The value in each node is greater-than or equal-to (for some comparison definition) the values in both of its children. So the item with the highest value (highest priority) is at the root of the tree.
The label of the parent of node i is i/2
The label of the left-child of node i is 2*i
The label of the right-child of node i is 2*i+1
If it helps you, draw the picture of the tree and manipulate stickies or pieces of paper to see how the algorithms for inserting and deleting nodes work.
Typically, we represent this heap as an ArrayList<T> with the first item (at index 0) unused (maybe null).
Add a HeapExamples class to your project.
Make three examples of the following heaps by defining an ArrayList<Integer> for each case in your examples class and an initHeaps method to add the values in the appropriate order.
To build the following heap
node-1
/ 70 \
/ \
node-2 node-3
/ 60 \ 40
/ \
node 4 node 5
35 50
we would proceed as follows:
ArrayList<T> myheap = new ArrayList<T>();
void initHeap(){
this.myheap.add(null); // the unused first item
this.myheap.add(70);
this.myheap.add(60);
this.myheap.add(40);
this.myheap.add(35);
this.myheap.add(50);
}
Here are the three heaps to define:
node-1
/ 80 \
/ \
node-2 node-3
/ 50 \ / 40
/ \ /
node-4 node-5 node-6
45 20 30
node-1
/ 50 \
/ \
node-2 node-3
/ 45 \ 40
/ \
node-4 node-5
30 20
node-1
/ 70 \
/ \
node-2 node-3
/ 45 \ / 50
/ \ /
node-4 node-5 node-6
30 20 40
Define the class ExamplesHeaps that will contain the tests for the methods you now design.
You can use the data defined in HeapExamples class for the tests of your methods.
Define the class PriorityQueue<T> that will represent a heap-based priority queue. It has two fields: an ArrayList<T> and a Comparator<T> that determines the ordering of priorities.
Design the method isLeaf that consumes a node label (an int) and returns true if the node has no children (remember the numberings...).
Design the method higherPriorityChild that consumes the index of a node that is not a leaf and produces the index of its child with the highest priority.
Note: If the node has only one child, then this will be the one with the higher priority, of course.
Design the method insert that inserts a new node into the heap.
Here is what we covered in the lectures:
Insert the new item at the next position in the bottom level (the end of the list representation). Say, this is position k.
Upheap from k:
While (k > 1 and heap(k) > heap(k/2)) {
~~~~~~swap heap(k) and heap(k/2)
~~~~~~set k to k/2
}
Design the method remove that removes the node with the highest priority from the heap.
Here is what we covered in the lectures:
save the root item as a temporary
move the last item into the root position
Downheap from k = 1:
While (k is not a leaf) {
~~~~~~find ck the node with the larger child of the node k
~~~~~~if heap(k) < heap(ck) {
~~~~~~~~~~~~swap heap(k) and heap(ck)
~~~~~~~~~~~~set k to ck }
~~~~~~else stop
}
Problem 2: Sorting Algorithms Detective
Finish the Lab 11 work on measuring time spent of different sorting algorithms and finding out from the timing and test behavior which algorithms could exhibit the observed behavior.
As it says in the lab description:
Run the program a few times with small data sizes, to get familiar with what it can do. Then run experiments and try to answer the following questions:
Which algorithms run mostly in quadratic time, i.e. O(n^2)?
Which algorithms run mostly in O(n.log_n) time?
Which algorithms use the functional style, using Cons lists?
Which algorithm is the selection sort?
Why is there a difference when the algorithms use a different Comparator?
Copy the results into a spreadsheet. You may save the result portion in a text editor with a .csv suffix and open it in Excel (or some other spreadsheet of your choice). You can now study the data and represent the results as charts.
Do so for at least three algorithms, where there is one of each —
a quadratic algorithm and a linear-logarithmic algorithm. Produce a report with a paragraph that explains what you learned, using the Excel charts to illustrate this.