Assignment #3 - Priority Queues and Adaptable Priority Queue
This assignment is not easy. It requires you understand the related data structures,
the algorithms, and it requires stong OO design. You
should read through the assignment to get a basic idea of the requirements
and then start working through the assignment in the recommended order.
Objectives:
The main objectives of this assignment are:
- Continue to analyze data structures using the @TimeComplexity annotations.
- See how we use List to build other data structures.
- Build an appropriate tree for a specific task.
- Provide you with a data structure implemented three different ways which
will be used for empirical comparisons in Assignment #4.
The Assignment:
The Concept:
This project is to build different variations of Priority Queues. In the
next assignment we will these queues to implement sort algorithms and
compare their time order.
Your Job:
You are to implement three Priority Queues, using list and complete tree
(stored with array, not linked structure):
- Develop an OrderedPQ data
structure using the DoublyLinkedList
created in Assignment 1. Class files OrderedPQ have been provided for
you. You should NOT change the class names, interfaces, or packages.
- Develop an UnorderedPQ data
structure using the DoublyLinkedList
created in Assignment 1. Class files UnorderedPQ have been provided for
you. You should NOT change the class names, interfaces, or packages.
- Develop an Heap using the ArrayList data
structure. You need to implement all the Methods include upheap and
downheap in the class file. HeapPQ also implements Adaptable PQ.
NOTE:
Ignore the package cs2321.sorting for now. CS2321.sorting is for the next
assignment.
Getting Started:
- Download and import the following zip file: Assignment3.zip.
For Eclipse:
- Open Eclipse
- Choose "File → Import"
- Select the "General" category
- Pick "Existing Projects into Workspace"
- Click on "Next"
- Select the button for "Select Archive File" and browse to/select the zip file.
- Click on "Finish"
- A new project has been added to the workspace: PriorityQueues,
which provides TestingPQ.java, a sample (but incomplete) test
platform, and three classes for potential Priority Queue implementations, OrderedPQ.java,
UnorderedPQ.java, and Heap.java, also
DefaultComparator.java. The net.datastructures
package contains all of the interfaces needed for this assignment (including
Entry, PriorityQueue ). There is also another package, sorting,
which has code for Assignment 4. It can be ignored for this assignment.
- Copy the List implementation and any additional required files you used
for Assignment 1 into your cs2321 directory for the project and use it to
build all three Priority Queues.
Submission:
First, look at the following checklist:
- Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
- Do you ever import from java.util. If so, be sure you only
import allowed components (like Iterator, Exceptions, etc.). Unless
the assignment specifically mentions it is permissible, you should never include
any of java's native data structures.
- Does the program meet all required interfaces?
- Do all your methods have a @TimeComplexity indicator?
- Do you provide adequate TCJ comments
to prove your time complexity?
- Is the indentation easily readable? You can have Eclipse correct indentation
by highlighting all code and select "Source → Correct Indentation".
- Have you removed any of the "cs2321" comments (/*#) that you
may have accidentally copy/pasted?
- Are comments well organized and concise?
If you have reviewed your code and all the criteria on the checklist are acceptable,
follow the submission procedure.
Grading Criteria:
- An OrderedPQ and an UnorderedPQ that correctly implement all methods and interfaces: 40
- An Heap that correctly implement all methods and interfaces: 40
- Correct documentation of time complexity: 10
- Clear concise code with good commenting including the time complexity
justification: 10