Assignment 2: Class Hierarchies and Working with Specifications

Due: Tuesday, Nov 8 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.

1Articulating and Testing Axioms (Standard and Advanced)

This section describes three fundamental datatypes that access elements of a collection in different orders. We have given you the informal description of the properties. Your job is twofold:

• State the axioms on interactions between operations for each datatype. If you are unsure as to the style of an axiom, recheck the class notes. Put your answers in a text file called axioms.txt.

• Write a set of test cases that would thoroughly check whether an implementation of the ADT satisfies your axioms. This question is about coverage of the cases you need to consider, not about the sheer number of tests that you propose. Write these as complete test cases against the Tester library we are using this term. You may put all of your test cases in a single Examples class.

For this assignment, we will assume each ADT is over numbers. Do not worry about error handling (like trying to remove an element from an empty data structure).

You are not being asked to implement any of these ADTs. You are merely stating axioms and defining test cases.

1.1Priority 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.

1.2Stacks

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

Example: Assume that we added elements 7, 4, and 5 to a new stack (in that order). Calling pop would produce a stack containing 4 and 7. Calling top on that stack would produce 4. Calling pop on that stack again would produce a stack containing 7.

1.3Queues

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 stacks are:

• newQ: -> Queue // produces a Stack 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

Example: Assume that we added elements 7, 4, and 5 to a new queue (in that order). Calling dequeue would produce a queue containing 4 and 5. Calling front on that stack would produce 4. Calling dequeue on that stack again would produce a stack containing 5.

2Class 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?

3Implementing AVL Trees (Advanced)

Friday’s lecture began discussing AVL trees, a form of balanced binary-search trees. Your tasks are to:

1. Provide a class that implements the ISet interface using the AVL-tree data structure.

2. Write a method isAVL that tests whether a given binary tree is an AVL tree (put this in your Examples class).

3. 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).