## CSE 131 Module 8: Abstract Data Types

Important!

Before beginning any work, do a Team...Pull in your repository.

### 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 test-driven 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: x100 + 5. This polynomial has two terms:

• One term is the constant 5, which is technically 5x0: a term with coefficient 5 and degree 0.
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.

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.

• 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.
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:
• 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.
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:
• 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.
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.
• 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.
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!

• You must commit and push all of your work to your repository. It's best to do this from the top-most 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.

When you are done with this lab, you must be cleared by the TA to receive credit.
• Do a Team…Pull to update your repository. You must do this or the commit/push below may fail.
Make certain this has worked by logging into bitbucket. There you will see the commit(s) in your news feed if it was successful. You can also check the Source page to locate and ensure your code was received.

It is your responsibility to make certain the code has been pushed. Some of your work receives credit through testing of your pushed code. You will receive no credit for such work if you failed to push. We generally reserve the right to revoke credit for any of your work that has not been pushed on-time.

• 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 the TA's 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
 Last name WUSTL Key Propagate? (NOT your numeric ID) Do not propagate lower case only e.g. Smith j.smith 1

Acknowledgements and assertion of integrity