CSE 131 Module 8: Abstract Data Types



In this lab, you will using one ADT (Abstract Data Type), provided in the Java library, as the basis for creating an implementation of a new ADT (a Polynomial).

Some useful documentation:

We are interested in representing polynomials, each of which is a sum of terms. These terms are all powers of some unknown (denoted as x). Our implementation will be sparse, in the sense that we will not represent terms of the polynomial that have coefficents of 0. As review and to illustrate the sparse nature of our representation, example consider the polynomial: x100 + 5. This polynomial has two terms:

There are many terms between the x0 and x100 terms that do not appear in the polynomial as written above. It would be tedious and unnecessary to write all of those terms:
1 x100  + 0 x99  + 0 x98  + 0 x97 + …  + 0 x2  + 0 x1  + 5 x0
Moreover, all terms of degree higher than 100 cannot possibly be shown, because they are inifinite in number, starting with 0 x101. A dense representation of our polynomial would require explicitly listing all of the terms, between x0 and x100, including those with 0 as their coefficient. Our sparse representation will elide most, if not all, of the terms with 0 as their coefficient.

Story to help you create the Term class.

We begin with a simple class such as the ones you designed in studio. You can drive your development from this story and from the supplied unit test TermTest.

A Term has-a coefficient, which is a double, and a degree, which is an integer. The term c xd is represented by coefficient c and degree d. The Term class is immutable, a word that here means unchanging. You enforce this in your implementation by declaring the instance variables to be final.

A Term can be evaluated at a particular value of x, returning a double as the result of that computation. Recall that exponentation of xd can be computed in Java as Math.pow(x,d).

This would be a good time to develop your Term implementation, testing as you go, until all of the tests in TermTest pass.

We will be automatically testing your work, so do not change the TermTest unit test! You should make your implementation conform to pass the test, not the other way around.

On to SparsePolynomial

In your lab8 package you will also find the following, analagous to Set and HashSet described above.

Follow the advice below in terms of implementation stragegy. It will save you time. You must have completed Term above and have it passing its tests before you should move on.
  1. Throughout this process you will run SparsePolynomialTest as you go, so that you can develop your code as guided by the test.
  2. Go ahead and run it now, as a JUnit test. All the tests should fail.
  3. Work on testOnlyOneInstanceVar(), which requires that you have exactly one instance variable in SparsePolynomial as follows: You are not allowed any other instance variables: this test will not pass if you declare more. This kind of restriction is unusual in development, but it supports the concepts we want you to learn in this assignment.
  4. You must instantiate an implementation of Set<Term> in the constructor, and we are using HashSet<Term> as the implementation. Once you have done this properly, testInit() should pass.
    There is no explicit test for hashCode() or equals(Object), so at this point please generate them automatically, as you did in studio, basing those methods on the only instance variable you should have in this class, namely your Set<Term>.
  5. Your constructor must do more than instantiate the HashSet. It is provided an array of Term. These should be added to your HashSet<Term> as follows:
  6. Time-saving tip There are more methods to implement, and while you could type in each one, there is a quick way to generate them all as stubs.
  7. Next implement degree() so that testDegree() passes.
  8. Implement toArray(), which generates the every-term dense representation as an array from the sparse representation using a Set. The testToArray() test should pass.
  9. Now implement evaluate(x), remembering that each Term can evaluate itself at a given value of x. At this point, testEval1() and testEval2() should pass.
  10. Next implement sum(Polynomial other).
    It's worth thinking through how to do this without writing a lot of code. You can use methods you've already written to help here, such as toArray().
    Now testSum() should pass.
  11. Forge ahead with derivative and when it's working, testDerivative() should pass.
  12. Make sure the testZeros() and testOneMissingTerm() are passing.
Make sure all the tests are passing and that you commit and push your work so we can grade it!

Submitting your work (read carefully)

Last modified 15:04:03 CDT 30 October 2017
When you done with this lab, you must be cleared by the TA to receive credit.

This demo box is for lab 8
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
lower case only
e.g. Smith j.smith

Acknowledgements and assertion of integrity

You must select one of the options below
The work submitted here was performed in accordance with this course's policy on collaboration.
On your honor, you have neither given nor received any unauthorized aid on this assignment.

However, the following TAs, students, or professors were supportive in completing this assignment.
Their help was also in accordance with course policies.

Thanks to (leave blank if appropriate):

In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment.

You would like to be contacted by an instructor to facilitate staying on track in this course.

Comments about this:

You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment.

You would like to be contacted by an intructor to faciliate staying on track in this course.

Comments about this:

TA: Password: