CCCS $315$: Data Structures and Algorithms

Assignment $3$

Type of Assignment

$$ Individual Work

$$ Estimated Time: $160$ minute

Description

In this Assignment, you will examine the Priority Queue libraries to solve a business problem as well

as implement and analyze a variation of the heap data structure.

Learning Outcomes

$$ Recognize the use of the Priority Queue and Heap datastructures

$$ Apply Big$-$O notation to analysis of an algorithm

Evaluation

Points

$10$ Code formatting and citations

$11$ Part $1$ Implement a stack using the sorted priority queue

$11$ Part $2$: Implement a queue using a priority queue

$10$ Part $3$: Implementation and Analysis of a Four$-$Heap

$42$ Total

Submitting your work

Work is to be submitted through MyCourses. Please validate that your ZIP files contain both $.$java and

$.$class files prior to submitting. Submissions lacking source code cannot and will not be marked.

Part $1$: Implement a stack using a priority queue

Objective

Using the skeleton class SortedPriorityQueueStack provided, implement a stack abstract data type

using only a sorted priority queue and one additional integer instance variable. Analyze the Big$-$O

runtime of your implementation of the push$()$ and pop$()$ methods.

Requirements

$1.$ Your solution should use the textbook net.datastructures.SortedPriorityQueue

$2.$ Skeleton classes and JUnit test cases are provided to support your implementation. These

skeletons should be implemented however additional methods may be required.

$3.$ Implement proper error handling

$4.$ The Big$-$O runtime of the push$()$ and pop$()$ should be indicated in the code comments

Points

Points Method

$2$ public SortedPriorityQueueStack constructor and body

$3$ public void push$($V value$)$

$1$ point for Big$-$O analysis

$3$ public V pop$()$

$1$ point for Big$-$O analysis

$1$ public V top$()$

$1$ public int size$()$

$1$ public boolean isEmpty$()$

$11$ Total

Part $2$: Implement a queue using a priority queue

Objective

Using the skeleton class UnSortedPriorityQueueQueue provided, implement a queue abstract data

type using only an unsorted priority queue and one additional integer instance variable. Analyze the BigO runtime of your implementation of the enqueue$()$ and dequeue$()$ methods.

Requirements

$1.$ Your solution should use the textbook net.datastructures.UnSortedPriorityQueue

$2.$ Skeleton classes and JUnit test cases are provided to support your implementation. These

skeletons should be implemented however additional methods may be required.

$3.$ Implement proper error handling

$4.$ The Big$-$O runtime of the enqueue$()$ and dequeue$()$ should be indicated in the code comments

Points

Points Method

$2$ public UnSortedPriorityQueueQueue constructor and body

$3$ public void enqueue$($V value$)$

$1$ point for Big$-$O analysis

$3$ public V dequeue$()$

$1$ point for Big$-$O analysis

$1$ public V first$()$

$1$ public int size$()$

$1$ public boolean isEmpty$()$

$11$ Total

Part $3$: Implementation and Analysis of a Four$-$Heap

This question is inspired from the University of Washington$$s cse$373.$

Objective

The goal of this part of the assignment is to analyze a generic, four min$-$heap. A four min$-$heap is similar

to a binary min$-$heap but each node can have up to four child nodes. In your analysis, you will assume

that the FourHeap implements the generic PriorityQueue interface and maintain both the heap

structure and the minimum heap order property. We will also assume that your FourHeap uses an array

like we have for net.datastructures.HeapPriorityQueue. However, the computations to find the

index of a node's children and parent will be different.

Please answer the following questions and submit in a text document, a$3$q$3.$txt

$1.$ Given the array$-$based implementation of the four$-$heap, please implement the following

methods using inspiration from net.datastructures.HeapPriorityQueue:

$$ protected int parent$($int j$)$

$$ protected int left$($int j$)$

$$ protected int right$($int j$)$

$2.$ On inserts, do you expect net.datastructures.HeapPriorityQueue or FourHeap to

perform better? Explain why.

$3.$ On remove, do you expect net.datastructures.HeapPriorityQueue or FourHeap to

perform better? Explain why.

Be aware that I am providing a full skeleton to help in your comprehension of the four$-$heap. A full

solution of this skeleton does not need to be returned.

Requirements

$1.$ Answers and justification to this part$$s question$$s should be present in file a$3$q$3.$txt

Points

Points Method

$2$ protected int parent$($int j$)$

$2$ protected int left$($int j$)$

$2$ protected int right$($int j$)$

$2$ Analysis of insert performance of four$-$heap vs binary heap.

$2$ Analysis of removeMin perfoance of four$-$heap vs binary heap.