Assignment 2: Class Hierarchies and Working with Specifications
Due: Tuesday, Nov 6 at 11:59pm via Turnin
There are three sections of problems in this assignment: the first is for both the standard and advanced options, the second is for the standard option, and the third is for the advanced option.
1 Testing Data Structure Implementations
This section describes three fundamental datatypes that access elements of a collection in different orders. We have given you the types of operations for the datatype, a description of the datatype’s properties, and an example sequence of operations. For this assignment, we will assume each ADT contains numbers (rather than Strings, as we did for sets and bags in lecture).
Your job is write a collection of test cases that would determine whether a supposed implementation of each datatype satisfies its properties. If we ran your tests against a correct implementation of the datatypes, all of your tests should pass. More interestingly, if we ran your tests against an incorrect implementation of a datatype, then at least one of your tests should fail. Thus, this question is about how well your tests cover the expected behavior of the datatype; it is not about the sheer number of tests that you propose.
Provide a file Examples.java containing a single Examples class with all of your tests, written as checkExpects against the Tester library. The names of your test methods should indicate the data structure being tested: use method names testQueue, testStack, and testPQ as the prefixes for your test case names. Do not worry about tests on undefined cases that would yield errors (like trying to remove an element from an empty data structure).
Compile your Examples.java file against this file of interfaces and dummy classes to make sure you match the names we’ll assume when grading your work. Note that the classes given in the dummy file are broken. Your test cases will fail against the dummy file. What matters is that your code compiles when using the dummy file.
You are not being asked to implement any of these ADTs. You are merely defining test cases and interfaces. The challenge in this assignment lies in figuring out how to develop a good set of test cases given only a description of the operations and the general properties. You should nevertheless make sure that your file at least compiles (as we will do the same when we evaluate your test suite).
1.1 Queues
A Queue is an ADT for accessing elements of a set in the order of least-recently added to most-recently added (otherwise known as "first in, first out", or FIFO-order). The operations on queues are:
newQ: -> Queue // produces a Queue with no elements
enqueue: Queue, int -> Queue // adds element
dequeue: Queue -> Queue // remove least recently-added element
front: Queue -> int // return, but don’t remove, least-recently added elt
1.2 Stacks
A Stack is an ADT for accessing elements of a set in the order of most recently added to least-recently added (otherwise known as "last in, first out", or LIFO-order). The operations on stacks are:
newStk: -> Stack // produces a Stack with no elements
push: Stack, int -> Stack // adds element
pop: Stack -> Stack // remove most recently-added element
top: Stack -> int // return, but don’t remove, most-recently added elt
1.3 Priority Queues
A Priority queue is an ADT for accessing elements of a set in order. Elements may be added to a priority queue in any order, but elements may only be removed in order from smallest to largest. The operations on priority queues are:
newPQ: -> PriorQ // produces a priority queue with no elements
addElt: PriorQ, int -> PriorQ // adds element
remMinElt: PriorQ -> PriorQ // remove smallest element
getMinElt: PriorQ -> int // return, but don’t remove, smallest elt
Example: Assume we added elements 7, 4, and 5 to a new priority queue (in that order). Calling getMinElt on the resulting priority queue should return 4. Calling remMinElt should produce a priority queue containing only 5 and 7.
2 Class Hierarchies (Standard)
A new vehicle-rental company, BumpyRidez, is creating software to manage rental prices and maintenance information on its fleet of vehicles. The lead software developer’s Java skills are as rough as the rides on the vehicles. This file shows his start at creating a class hierarchy for their needs. From this file, we see:
Some vehicles are considered luxury items and have a premium associated with their rental cost.
Some vehicles have conventional engines and need periodic oil changes.
Some features are unique to individual kinds of vehicles.
Your job is to clean up this mess of a class hierarchy. You should keep all of the concepts in the starter file, but you may create additional classes and interfaces, remove inherited fields that make no sense for a particular type of vehicle, etc.
Your cleaned up code should enable BumpyRidez to expand into new kinds of vehicles in the future, without editing the code that you create now. We hear they are seeking suppliers of parachutes and hang-gliders (which have their own maintenance issues when the fabric rips), and perhaps some other bump-inducing rides that you can imagine...
In addition to the code, submit answers to the following questions either as a comment (if you are submitting a single file) or in a separate file called questions.txt (no Word or PDF files, please!)
What criteria did you use to decide whether to capture each concept as a class, abstract class, or interface.
How does your code enable extensions in the longer term?
3 Implementing AVL Trees (Advanced)
Friday’s lecture began discussing AVL trees, a form of balanced binary-search trees. Your tasks are to:
Provide a class that implements the ISet interface using the AVL-tree data structure.
Write a method isAVL that tests whether a given binary tree is an AVL tree (put this in your Examples class).
Provide test cases for both isAVL and your AVL-tree implementation.
In addition, please submit answers to the following questions (either as a comment in your file or in a separate questions.txt file):
Explain in precise prose how your implementation guarantees that the tree is always balanced. For each operation that returns an AVL tree, indicate if/how it uses the assumption that the original tree is indeed balanced.
Explain in precise prose how your implementation guarantees that the tree is always a binary search tree. For each operation that returns an AVL tree, indicate if/how it uses the assumption that the original tree is indeed a binary search tree.
Did you use isAVL in testing your AVL-tree implementation? Describe how this either was or could have been useful (if you did not use it).