Background
Read Section 3.1 in the textbook for background on polynomials and polynomial arithmetic.
A polynomial may be represented using a linked list as follows: for every term in the polynomial there is one entry in the linked list consisting of the terms coefficient and degree. The entries are ordered according to ASCENDING values of degree, i.e. lowest degree term first, then next lowest degree term and so on, all the way up to the highest degree term. IMPORTANT: Zero-coefficient terms are NOT stored.
For example, the following polynomial (the symbol ^ is used to mean raised to the power):
4x^5 2x^3 + 2x +3
can be represented as the linked list of terms:
(3,0) -> (2,1) -> (-2,3) -> (4,5)
where each term is a (coefficient,degree) pair.
Notes about representation:
Terms are stored in ASCENDING order of degrees from front to rear in a non-circular linked list.
Zero-coefficient terms are NOT stored.
An EMPTY (zero) polynomial is represented by a linked list with NO NODES in it, i.e. referenced by NULL.
Coefficients are floating point numbers
Degrees are POSITIVE integers, except if there is a constant term, in which case the degree is zero.
There will not be more than one term in the same degree.
If you do not represent all your polynomials (the initial inputs as well as those you get out of doing arithmetic on polynomials) as above, you will lose credit even if your results are mathematically correct.
Implementation and Grading
Download the attachedpolynomial_project.zipfile to your computer. DO NOT unzip it. Instead, follow the instructions on the Eclipse page under the section Importing a Zipped Project into Eclipse to get the entire project into your Eclipse workspace.
You will see a project calledPolynomialwith the following classes in packagepoly:
Node
Term
Polynomial
Polytest
(Aside from these, there are also three sample input files, described in theRunning the Programsection below.)
You need to complete the implementation of thePolynomialclass where indicated in the following methods:
Method
Grading Points
evaluate
10
add
25
multiply
25
Efficiency is not a requirement for any of the methods. And, you can useMathclass methods as needed.
Note: You will get a zero if you use any other data structure (e.g. array/arraylist)anywherein your implementation, foranyreason, even if it has nothing to do with the actual polynomial operations. You must work with linked lists ONLY all the way through.
Do not changeNodeandTermin any way. You will not be submitting them, and we will be using the original versions to test yourPolynomialimplementation.
If you wish to changePolytest, feel free. You will not be submitting it, and we will not be using it to grade yourPolynomialsubmission.
Observe the following rules while working onPolynomial.java:
Only fill in the code in the methodsadd,multiply, andevaluatewhere indicated.
In methods that return aPolynomial(addandmultiply), the polynomial that is returned must be represented as described in the Notes about representation part of theBackgroundsection above.Your method will not get creditif the returned polynomial does not adhere to this representation, even it is mathematically correct.Also see the Notes about empty (zero) polynomials at the end of theRunning the programsection below.
DO NOTremove thepackageline at the top of the file.
DO NOTremove any of theimportstatements.
DO NOTadd any import statements.
DO NOTchange the headers of ANY of the given methods
DO NOTchange/remove any of the given class fields
DO NOTadd any new class fields.
YOU MAYadd new helper methods, but you must declare themprivate.
Before you submit, make sure to check your code against the originalPolynomial.java,Term.java, andNode.javafiles to make sure you have adhered to the rules above.
Running the program
There are three sample input files for you to test (they should be under the project folder in Eclipse):
A fileptest1.txtthat contains the polynomial
4x^5 2x^3 + 2x + 3
A fileptest2.txtthat contains the polynomial
8x^4 + 4x^3 3x + 9
A fileptest1opp.txtthat contains the polynomial
-4x^5 + 2x^3 2x 3
(the negation of the polynomial inptest1)
In each of these files, each line is a term, with the first value being the coefficient, and the second value being the degree. The terms are listed indescendingorder of degrees and the respective non-zero coefficients. Remember that when you store a polynomial in a linked list, you will store it inascendingorder of degrees. (This is actually already implemented by the Polynomial constructor when it reads a polynomial from an input file. All you have to do is make sure you stick with this rule when you add and multiply.)
You may assume that we will NOT test with an invalid polynomial file, i.e. every test input file will either have at least one term in the correct format, or will be empty (seeNotes about empty (zero) polynomialsbelow). So you dont need to check for validity of input.
Heres a sample run of the driver,Polytest. Apart fromptest1.txt,ptest2.txt, andptest1opp.txt, a fourth test polynomial file,ptestnull.txtis also used. This is an empty file that stands for a null (zero) polynomial you will need to create this yourself. See notes after the test run for special instructions regarding zero polynomials.
Enter the name of the polynomial file => ptest1.txt
4.0x^5 + -2.0x^3 + 2.0x + 3.0
1. ADD polynomial
2. MULTIPLY polynomial
3. EVALUATE polynomial
4. QUIT
Enter choice # => 1
Enter the file containing the polynomial to add => ptest2.txt
8.0x^4 + 4.0x^3 + -3.0x + 9.0
Sum: 4.0x^5 + 8.0x^4 + 2.0x^3 + -1.0x + 12.0
1. ADD polynomial
2. MULTIPLY polynomial
3. EVALUATE polynomial
4. QUIT
Enter choice # => 1
Enter the file containing the polynomial to add=> ptest1opp.txt
-4.0x^5 + 2.0x^3 + -2.0x + -3.0
Sum: 0
1. ADD polynomial
2. MULTIPLY polynomial
3. EVALUATE polynomial
4. QUIT
Enter choice # => 1
Enter the file containing the polynomial to add=> ptestnull.txt
0
Sum: 4.0x^5 + -2.0x^3 + 2.0x + 3.0
1. ADD polynomial
2. MULTIPLY polynomial
3. EVALUATE polynomial
4. QUIT
Enter choice # => 2
Enter the file containing the polynomial to multiply=> ptest2
8.0x^4 + 4.0x^3 + -3.0x + 9.0
Product: 32.0x^9 + 16.0x^8 + -16.0x^7 + -20.0x^6 + 52.0x^5 + 38.0x^4 + -6.0x^3 + -6.0x^2 + 9.0x + 27.0
1. ADD polynomial
2. MULTIPLY polynomial
3. EVALUATE polynomial
4. QUIT
Enter choice # => 3
Enter the evaluation point x=> 2
Value at 2.0: 119.0
1. ADD polynomial
2. MULTIPLY polynomial
3. EVALUATE polynomial
4. QUIT
Enter choice # => 4
The sample tests we have given you are just for starters. You will need to create other tests of your own on which you can run your code. For every test you run, be careful to keep your test input in the same format as the test files provided, otherwisePolytestwill not work correctly. And make sure your test file is in the same folder as the other files, i.e. underPolynomial.
Note on translation from internal to output representation:
ThetoStringmethod in thePolynomialclass returns a string with the terms in descending order, fit for printing. (It processes the ascending ordered terms of the input linked list in reverse order.) For illustration, see how theaddmethod inPolytestprints the resulting polynomial:
System.out.println(Sum: + Polynomial.toString(Polynomial.add(poly1,poly2)) +
);
Notes about empty (zero) polynomials:
If you want to test with an empty polynomial input, you should create a file with nothing in it. In Eclipse, you can do this by right clicking on the project name in the package explorer view, then selectingNew, then selectingFile. Give a name, and clickFinish. You new file will show up under the project name folder in the package explorer view, and the file will be opened in the text editor view. But dont type anything in the file.
Remember that when you add two terms of the same degree, if you get a zero coefficient result term, it should not be added to the result polynomial. As listed in the Notes about representation in theBackgroundsection, zero-coefficient terms are not stored.
The string representation of a zero polynomial is 0 see thetoStringmethod of thePolynomialclass. So, thePolytestdriver will print a zero for a zero polyomial input, or a zero polynomial that results from an operation performed on two polynomials.
Reviews
There are no reviews yet.