Assignment 11

Instructions

The names of the classes must be exactly the same as specified. The same is the case for the names and types of the fields within the class, as well as the order in which they are defined and listed as the constructor arguments. This allows us to design our own Examples class that tests your program.

Make sure you follow the style guidelines that WebCAT enforces. For now the most important ones are: using spaces instead of tabs, indenting by 4 characters, following the naming conventions (data type names start with a capital letter, names of fields and methods start with a lower case letter), and having spaces before curly braces.

You will submit this assignment by the deadline using the Web-CAT submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the WebCAT system may slow down to handle many submissions - so try to finish early.

With each homework you will also submit your log file named pair-user1-user2.txt where you replace user1 and user2 with the usernames of the two partners.

On top of both files you will have five lines of comments as follows:

(In the text file you do not need the two slashes)

There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem wou work on.

The three submissions will be organized as follows:

• Submission HW11P1: The log file and the solution to the Priority Queue problem using the tester library or JUnit for the tests – in one .zip file

• Submission HW11P2: 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 2nd, 11:59 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 ExamplesHeap 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:

  heap1:

  node-1

  /   80   \

  /          \

  node-2         node-3

  / 50 \         / 40

  /      \       /

  node-4   node-5  node-6

  45       20      30

  heap2:

  node-1

  /  50  \

  /        \

  node-2      node-3

  /   45  \       40

  /         \

  node-4      node-5

  30          20

  heap3:

  node-1

  /   70  \

  /         \

  node-2         node-3

  / 45 \         / 50

  /      \       /

  node-4  node-5   node-6

  30      20      40

• Use the data defined in ExamplesHeaps class for the tests of your methods.

• Define the class PriorityQueue<T> that will represent a heap-based priority queue. It has two fields: alist which is 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

    }

Heapsort

Now implement a simple variant of heapstort as follows:

In the class HeapSort implement the method

public ArrayList<T> heapsort(ArrayList<T> alist, Comparator<T> comp)

that consumes the ArrayList to be sorted} and a Comparator. In the first step just insert the given data into a new PriorityQueue, one item at a time.

In the second step, the remove the data from your PriorityQueue and insert them into the resulting ArrayList, one at a time.

If you just add each item at the end, you will end up with a list ordered in descending order.

Note: This is a simplified heapsort - real heapsort does not need additional space and results in a correcly ordered list.

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.