We can define an abstract data type for single-variable
polynomials (with non-negative exponents) by using a list. Let
. If most of the coefficients ai are nonzero we could
use a simple array to store the coefficients and write routines to perform
addition, subtraction, multiplication, differentiation, and other operations on
these polynomials.
An array implementation would be adequate for dense
polynomials, where most of the terms are present, but if
and
, then the running time is likely to be unacceptable. One
cans see that if arrays were used, then most of the time is spend multiplying
zeros and stepping through what amounts to nonexistent parts of the input
polynomials. This is always undesirable.
An alternative is to use a singly linked list. Each term in
the polynomial is contained int one cell, and the cells are stored in
decreasing order of exponents. For instance, the linked lists below represent
and
.

In this class, we will be doing automatic grading for part of your grade for all projects. This makes grading more fair for you the students, and it makes it easier for us to grade 110 projects. Your project's functionality will be graded automatically, while your programming style as well as your readme will be graded by hand.
Because this is such a large class, and also for the automatic grading, there will be strict guidelines as to exactly what needs to be handed in, and how it should be handed in. You will receive details for this soon, but we will specify here what info you will need at least to get started in programming this project.
You will notice from the grading scale of this project (see bottom of page) that you get points for a readme, code style, and functionality of your program. The following briefly describes each. Check back soon as we will be adding to the website general guidelines to be followed in each project
For now, know that you will need to turn in a neat, stapled hard copy of your code as well as printed documentation html files generated by javadoc. You will be required to submit your project electronically as well for automatic grading (see seciton below).
Part of the specification will be given to you in the form of a java interface. You will write a class which must implement this interface, which means that your class must at least have methods that match the ones in the interface definition (of course it can have more methods and variables as well). Because both the concepts of coding as PART of a program and using interfaces in java are probably new to a lot of you, we will be providing a testing environment for your code for this project only. This will let you test if your class implements the interface properly as well as give you an example of what the bigger program (the automatic grader) your code will be plugged into will look like.
You will be required to submit a class that will plug into the automatic grader. You will also be required to submit an application that demonstrates and tests the key functionality of your implementation.
The interface file you have to implement is Polynomial.java. You will have to create a class that implements this interface and write methods that correspond to the methods in this class. Notice also that Polynomial.java implements StudentSolution.java which has just 2 methods that will give us your name and email address. You will need to implement these methods in your derived class as well (note that you won't have to specifically put StudentSolution in your implements clause since it is inherited by Polynomial). If you don't implement all of these methods then Java will give you an error. Look inside the files Polynomial.java nd StudentSolution.java to get more details of exactly what each method is supposed to do.
Since many of you will be new to interfaces, we have also provided a sample solution to the problem that implements the Polynomial interface. You can download it here. This is a class called StupidSolution. It is called that because it is not the right solution. It implements the program incorrectly. It is just there so you can get a feel for how to implement an interface. With the interface specs above, you also downloaded a test program called PolyTest, which is a simple GUI interface created by Scott Stoness (a grad student) to allow you to test your Polynomial class. To use it, you will need to put all of your code for your class in the directory above the grader subdirectory. If you want to try it with StupidSolution, your directory should have StupidSolution.java, StupidSolution.class, and a subdirectory called grader with all of the files you downloaded before. To run the program, you have to run it from the directory where StupidSolution is. You just need to put java grader.PolyTest to run it. This notation is there because the interfaces and the PolyTest program are in a package called grader. You really don't need to understand packages to plug in your own assignment, though. Also, in case you have to recompile the grader package for some reason (you shouldn't because you should not change the code in grader, especially the interfaces) you just do javac grader/*.java.
A final note: DO NOT change the interface files (Polynomial.java and StudentSolution.java)! if you do so, your class will not be compatible with the automatic grader and you will get a very bad grade! You will only turn in the contents of your directory, nothing from the grader directory.
public String getName();
This method returns your name as it appears in the class roll.
public String getEmail();
This method returns the email address you would like your
score sent to.
public void zeroPolynomial();
This method resets the polynomial to 0.
public void insertTerm(double coef, int exp);
This method will insert a term into the polynomial. If a term
for the given exponent (exp) already exists, it is overwritten.
public Polynomial add(Polynomial rhs);
This method will add the polynomial to the polynomial given as rhs
and return the new polynomial. Note: The polynomial that this method
occurs in should not be affected by this method. You should put
the results in a new polynomial and not touch either of the ones
you are adding. this is very important!
public Polynomial multiply(Polynomial rhs);
This method will multiply the 2 polynomials and return the answer. It should
work the same as the add method and not change either of the original
polynomials.
public double getCoefficient(int power);
Given an exponent (power) this will return the coefficient of the
corresponding term. Note: if no term exists for this power, then
the coefficient returned should be 0.
public int getFirstExpGE(int power);
This method should, given an exponent, return the first exponent
in the polynomial greater or equal to power, which has a non-0 coefficient.
If there is no such power, then your routine should return -1.
For example, if you have the polynomial 2.0x^5 + -3.0x^2 + 9.0x + 3
then getFirstExpGE(0) should give you 0 (since there is a term for
the zeroth power, namely 3). getFirstExpGE(1) = 1 (since there
is a term for 1). getFirstExpGE(3) = 5, since there is no 3 term
and the next one up is 5 (2.0x^5). and getFirstExpGE(6) = -1 (there is
no term greater than or equal to 6).
public String toString();
This method is very very very important. It must be implemented
exactly according to these specification in order for the automatic
grader to work. Basically, we need everybody's string version of their
polynomial to look exactly the same so we can grade it automatically.
This method will return the string version of the polynomial. The rest of
this will describe what that should look like. Pay attention to everything
here, even the spaces have to be exact. Here are the rules:
Readme 10%
Code Style 20%
Functionality 70% (10% for each of the 7 implemented methods, excluding
getName() and getEmail())
Extra Credit : 10% derivatives (it is your responsibility to point out
extra credit done in the readme file)
Grading rules of thumb for "scrap code" : (Readme & boiler
plate code is worth 20% total for project, Readme & Code that does not
compile gets 30% total for project, Readme & code that compiles but does
not run gets 40% total for project.)
NOTE : WE USE THE TURN IN SCRIPT - NO EXTENSIONS - ONE SECOND LATE IS TOO
MUCH - YOU HAVE BEEN WARNED. DO NOT EMBARRASS YOURSELF BY ASKING FOR
EXTENSIONS.