1 Testing Data Structure Implementations
1.1 Queues
1.2 Stacks
1.3 Priority Queues
2 Class Hierarchies (Standard)
3 Implementing AVL Trees (Advanced)

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

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 queue would produce 4. Calling dequeue on that queue again would produce a queue containing 5.

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

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