CSE 131 Module 8: Abstract Data Types
Lab

Update your repository as usual using Team…Pull.
You should see a lab8 package in the labs source folder.
 As in
studio,
you will
develop your solution for this assignment using
testdriven development.
In the words of Plankton, this
plan cannot possibly fail.
 This is a new assignment, so if you run into trouble please let
the TAs or instructor know. Thanks in advance for your help
and patience.
 If you have a Set<Term> terms,
recall that you can iterate over the elements that set in no particular
order as follows:
for (Term t : terms) {
// t takes on each element of the set
}
Overview
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:
 Set is the ADT for a set. It is an interface,
which provsions for multiple implementations. Each such implementation
may be well suited for a given application scenario.
 HashSet
is one implementation of a Set and it is the one we will use for
this assignment.
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:
x^{100} + 5.
This polynomial has two terms:
 One term is the constant 5, which is
technically 5x^{0}: a term with coefficient 5 and degree 0.
There are many terms between the x^{0} and x^{100} terms that do not appear in the polynomial as written above. It would
be tedious and unnecessary to write all of those terms:
1 x^{100}
+ 0 x^{99}
+ 0 x^{98}
+ 0 x^{97}
+ …
+ 0 x^{2}
+ 0 x^{1}
+ 5 x^{0}
Moreover, all terms of degree higher than 100
cannot possibly be shown, because they are inifinite in number,
starting
with 0 x^{101}.
A dense representation of our polynomial would require explicitly
listing all of the terms, between
x^{0} and x^{100}, 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 hasa coefficient, which is a double, and
a degree, which is an integer.
The term c x^{d}
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 x^{d} 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.
 Polynomial is an ADT, implemented as an interface,
specifying the methods that an implementation must provide.
 SparsePolynomial is the implementation you will develop
for this assignment.
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.
 Throughout this process you will run SparsePolynomialTest
as you go, so that you can develop your code as guided by the test.
 Go ahead and run it now, as a JUnit test. All the tests should fail.
 Work on testOnlyOneInstanceVar(), which requires that
you have exactly one instance variable in SparsePolynomial
as follows:
 It must be private and final
 It must be of type Set<Term>
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.
 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>.
 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:
 Each Term has a coefficient and a degree. You should add
each Term to your HashSet except for those
that have a 0 coefficient.
 When you are finished processing the Term array, there
must be at most one entry in your Set of a given degree.
So what should you do if multiple terms have the same degree?
The unit tests must pass, but other than that, it's up to you in
situations like this where there is no specific requirement
for how to treat this situation.
 Timesaving 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.
 Locate the class name near the top of your SparsePolynomial
class.
 Notice that it has a red underline. This is because the class
claims to implement the Polynomial interface, but does not (yet).
 Mouse over the red underline and eclipse will suggest how to
fix this problem. Choose Add implmeneted methods.
 Now you have the methods you need to complete the work.
 Next implement degree() so that testDegree() passes.
 Implement toArray(), which generates the everyterm dense
representation as an array from the sparse representation using a Set.
The testToArray() test should pass.
 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.
 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.
 Forge ahead with derivative and when it's working,
testDerivative() should pass.
 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)
 You must commit and push all of your work to your repository. It's best to do this
from the topmost level of your repository, which bears your name and student ID.
 You must demo the commited work to a TA. Make sure the TA knows that
your demo is for credit at this point.
 Follow the directions below to have your demo for this work recorded.
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.
 Commit and push all your work to your repository
 Fill in the form below with the relevant information
 Have a TA check your work
 The TA should check your work and then fill in his or her name
 Click OK while the TA watches
 If you request propagation, it does not happen immediately,
but should be posted in the next day or so
This demo box is for lab 8