CS230 Data Structures, Wellesley College, Spring 2008

Assignment 5

Due before class (see schedule)

CS230 Home Page | Syllabus | Assignments | Documentation | CS Dept

Problem 1: Queue Implementation

Your book, in chapter 15, provides three different implementations for the Java Queue Interface. However, none of these implementations is complete. Some of the method implementations are left as programming projects. Study these three (partial) implementations. Choose one of them, complete it and test it, by providing implementations for the missing methods. You will use your Queue implementation in the next problem.

Problem 2: Symbolic Manipulation of Polynomials

In this problem, you will design and implement a program that creates and adds polynomials. A Queue will be used to store a representation of a polynomial.

Consider a polynomial such as the following:
3x⁴ + 2x³ + x² + 5x

It consists of four terms: 3x⁴, 2x³, x² and 5x. Notice that if a polynomial contains a final constant term, this term would be considered to have an exponent of 0.

Term Class

Each term is defined by two quantities, the coefficient and the exponent (for simplicity, assume that only a single variable, x, appears in the polynomial). Define a new Term class to represent polynomial terms. This class, should include two instance variables, to store the term's coefficient and exponent. Add a constructor, a method to provide the string representation of a term (how should it be named?), and the appropriate getters and/or setters, as you think appropriate. Also, add a main() method, to test your code in the Term class. Of course, feel free to define other methods, if you think appropriate!

Polynomial Class

An entire polynomial expression can be represented by a Queue, that holds objects of type Term. For example, the queue to represent the polynomial expression above, will contain four Term objects. The terms in the Queue should always be in order on the exponents. We reccommend to keep the polynomial in oder of decreasing exponents. In the above example, in that case, the head of the queue will be the term with coefficient 3 and exponent 4.

Define a Polynomial class, to represent polynomials. This class will have a single instance variable of type Queue to store its terms. Include the following instance methods in the Polynomial class:

a constructor to create an empty polynomial
a method to provide the string representation of a Polynomial type of object (How should it be named?)
addTerm(), which takes a Term as an argument, and adds it to this polynomial. Notice that the new term should be added in a way that preserves the ordering convention as described earlier. Furthermore, there should only be one entry in the Queue for each exponent.
addPolynomial(), which takes a Polynomial as an argument, and adds it to this polynomial. It should return the result of the addition. Naturally, the resulting polynomial should contain only one term for each exponent, and terms should be arranged in the right order. Think carefully about how this method can be implemented in a compact way.
a main() method to add some initial testing code, as you develop your class.

A Driver Class

Define a driver class to thoroughly test your code. As usual, the quality of your code, your testing effort and quality and program documentation will be a graded part of this task.
A sample run might look like this:

    Enter Polynomial P1: 
    4x^3 + 2x^2 + 5
    Enter Polynomial P2: 
    -2x^3 + 1x^2 + 3x^1
    The result of adding them is: 
    2x^3 + 3x^2 + 3x^1 + 5

We suggest that you use a scanner to read the user's input, and use the right delimiters to extract the interesting pieces of information from it, i.e., the coefficients and exponents. Please check the on-line Java documentation for the Scanner class. For an example on using a delimiter with a scanner, see Listing 4.9, in your book.

Add any more methods, auxiliary or otherwise, you may feel appropriate to make your overall design and code style work well. As usual, the quality of your code, your testing effort and documentation will be a graded part of this task.

Problem 3: Evaluating Implementation Strategies

In this problem, you will compare and evaluate two strategies for implementing the same task. In the /home/cs230/download/Assign5Sort directory you will find a file named JobSort.java that contains two methods, addJobArray() and addJobList(). Each of these two methods adds a PrintJob object to the collection of such objects, maintaining an order of increasing file size in the collection. In one case, the Collection used is an array, in the other, the collection used is a Linked List. Both methods assume that the array or list initially contain PrintJob objects that are already sorted by file size.

First summarize the two different implementation strategies in words, using plain English.

Then, consider the advantages and disadvantages of the two approaches: How effectively do they make use of resources such as memory space and time? With regard to time, how much computation is required for each implementation? (Keep in mind the way that Java accesses internally the nodes of a LinkedList.) What are the worst and best cases for the two implementations? Are there undesirable situations to either implementation?