Project 1: Priority Queue Testing

CSCI 313 Section 36, Spring 2018 | Due March 26, 2018

Your task for this project is to implement and analyze the performance of various types of priority queues. Here are the steps you should follow to complete this project:

Read this whole document before proceeding to actually doing step 2 (really, do it).

Write three different implementations of PriorityQueue interface (see below) with different approaches to insertion and removal of elements. Each of the implementations should be able to handle generic element types that implement the Comparable interface. The dequeue method in each of these implementations should remove and return an item of highest priority (i.e. you are implementing a Max-priority Queue).

Write generator methods for test data (or reuse the ones you wrote in the beginning of the semester). You should be able to generate many objects of type Task (see below) with randomly chosen priorities.

Design three performance benchmark methods that accept two parameters each: a PriorityQueue object and and an integer n the number of test data items to generate. Each of these methods should return the benchmark results in milliseconds.

benchmarkEnqueue(pq, n)

Generate n items of test data

Start the timer

Enqueue all of the test data into pq

Stop the timer and return the measured time.

benchmarkDequeue(pq, n)

Generate n items of test data

Enqueue all of the test data into pq

Start the timer

Dequeue all of the test data from pq

Stop the timer and return the measured time.

benchmarkEnqueueDequeue(pq, n)

Generate n items of test data

Create a random number generator for coin-flipping (see step iv.)

Start the timer

Loop over all of the test data, and on each iteration of the loop, simulate a coin flip by generating a random number and checking if it is divisible by two. If it is divisible by two, then enqueue the test item into pq; if it is not (and if pq is not empty), then dequeue one item from pq

Stop the timer and return the measured time.

Run each of these benchmarks using different amounts of test data for each one of the three priority queue implementations. For each combination of amount of test data and priority queue implementation, re-run the benchmark 10 times, sum up the benchmark results, and divide them by 10 to get a better estimation of average time (to avoid accidental inconsistencies).

Plot the results for later use in your report. You should end up with 9 plots (each of the three implementations benchmarked in three different ways). The horizontal axis of each plot should represent the amount of data used, and the vertical axis of the plot should represent the amount of time it took.

Write and print a report about the project. It should consist of the following (in order):

Your name (unless you prefer to not receive a grade)

What you were asked to write, how you plan to approach it

Big-theta complexity analysis (could be amortized) of enqueue and dequeue in each one of the implementations

All of the code that you wrote (in monospace font like Courier New or Roboto Mono see code below as an example)

Plotted and properly labeled results of benchmarks (optionally, you can add comments)

Your conclusions about the project (what you learned, what you observed etc.).

PriorityQueue interface

interface PriorityQueue> {

// Insert an element into the queue.

void enqueue(T item);

// Return (but do not remove) the element of highest priority in the queue.

T peek();

// Remove and return the element of highest priority in the queue.

T dequeue();

// Return the number of elements in the queue.

int size();

// Return true if there are no elements in the queue; false otherwise.

boolean isEmpty();

}

Task class

class Task implements Comparable {

public int id;

public int priority;

public int compareTo(Task other) {

return other.priority - this.priority;

}

}

The data structures

Heap-based Priority Queue

Implement an array-based heap as taught in class. Make sure to write convenience methods such as leftChildIdx, rightChildIdx, bubbleUp, bubbleDown etc.

Enqueue:

Insert the element at the end of the heap

Increase the size counter

Bubble up the newly inserted element

Dequeue:

Swap the first and last elements in the heap

Decrease the size counter

Bubble down the element that is currently the first

Return the element past the last one

Dynamic Array-based Priority Queue

It should have a helper boolean value called dirty, which will be used to indicate whether the internal array is sorted (clean) or not sorted (dirty).

Use @SuppressWarnings(unchecked) tag to avoid array-related compiler warnings (refer to the dynamic array implementation you saw earlier in the semester).

Enqueue:

Grow if the capacity is reached

Insert the element at the end of the array; increment the size counter

Set dirty value to true (because after this insertion, the array is not necessarily sorted).

Dequeue:

If the array is not sorted (i.e. it is dirty), sort in ascending order (lowest to highest priority). You can use Arrays.sort if you prefer (the only case in this whole project where you are allowed to use Javas collections library).

Return the element at the end of the array; decrement the size counter.

Doubly-Linked List-based Priority Queue

Enqueue:

Insert a node with the element into the underlying list in its ordered position (ordered by descending priority, i.e. highest priority comes first); increment the size counter.

Dequeue:

Remove the first node from the list and return the element inside of it (which should be of highest priority); decrement the size counter.