Assignment #4 - Priority Queues
This assignment may seem easy, but it requires strong 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 @SpaceComplexity and @TimeComplexity annotations.
- See how we use Sequences to build other data structures.
- Provide you with a data structure implemented three different
ways which will be used for empirical comparisons in Assignment #5.
- Build an appropriate tree for a specific task.
The Assignment:
The Concept:
Your job is to create and test a number of sorting algorithms over the
course of 4 weeks. The first part of this project is to build
different variations on Priority Queues to be used with the PQSort
algorithm presented in class.
Your Job:
You are to create three complete Priority Queues, using Sequences and a
Tree:
- Develop both an OrderedPQ and an UnorderedPQ
data structure using either the ArraySequence or
LinkedSequence created in Assignment 3. Class files
have been provided for you for the two implementations of
Priority Queues. You should
NOT change the class names, interfaces, or packages.
- Create a CompleteTree based on one of the implementations
talked about in class. This should implement the BinaryTree
interface, and two methods for mutation, removeLast(), and addLast().
- Finally, use the CompleteTree to build a Heap
data structure.
- You retain ownership of your Priority Queue implementations. It is
important that all operations work correctly so you can use them for
future parts of this project, as well as other projects.
Getting Started:
- Download and import the following zip file:
Assignment4.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 a test platform
(Main.java in the default package),
CompleteTree.java to base the Heap on, and
three classes for potential Priority Queue implementations,
OrderedPQ.java, UnorderedPQ.java, and
Heap.java. The net.datastructures package
contains all of the interfaces needed for this assignment
(including Sequence, PriorityQueue,
BinaryTree, and all of their
superinterfaces.
- Copy the implementation you used for the previous assignment
into your cs2321 directory for the project and use it to build the
first two Priority Queues.
- Consider the way you intend to use the CompleteTree for
your Heap and decide which implementation would be appropriate
for this project. Construct the CompleteTree, being careful to
include correct asymptotic analysis and justification. You also need to
provide analysis and justification for any new mutation methods you
create - for analysis of this class, you may assume the tree is always
complete, but you may not assume an order to the data.
- Use the Tree methods to create the Heap, implementing the private methods
bubbleUp() and bubbleDown() appropriately.
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?
- If any methods have a good amortized or expected cost, do they have both
the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
- Do all your data structures (and other classes like iterators) have a
@SpaceComplexity indicator?
- Do you provide adequate TCJ and SCJ comments
to prove your time and space 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: 30
- A CompleteTree implementing the BinaryTree interface, and including appropriate mutation methods (add, remove, and possibly swapElements): 20
- A Heap, built from the CompleteTree, that correctly implements all methods and
interfaces: 20
- Correct documentation of time and space complexity: 15
- Clear concise code with good commenting: 15