1 Articulating Axioms (Standard and Advanced)
1.1 Priority Queues
1.2 Stacks
1.3 Queues
2 Class Hierarchies (Standard)
3 Implementing AVL Trees (Advanced)

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.

1 Articulating 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:

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.1 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:

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

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

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:

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!)

3 Implementing 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):