JAVA Assignment : Polynomials
Polynomials 1 Introduction A polynomial is made of several terms, each term having a coefficient and a variable raised to a power. Polynomials are one-variable if all their terms contain only one variable. An example of such a polynomial is f(x) = 3x4 5x3 + 2x 4. This polynomial has four terms. The degree of a polynomial is defined as the highest power of the variable in a term. In the above example, the degree of the polynomial is 4. The polynomials we deal with have only positive, integral powers. The coefficients of our polynomials are also integral numbers. Two polynomials are the same if they contain the same terms. Several algebraic operations are possible with polynomials. The simplest one is evaluating the polynomial for a specific value of the variable. For example, for a polynomial f(x) = 3x4 5x3 + 2x 4, its value at x = 2.5 is defined as f(2.5) = 3 * (2.5)4 5 * (2.5)3 + 2 + (2.5) 4 which is 40.0625. Polynomials can be added together to create a new polynomial. The addition is performed by combining all the terms and adding the coefficients of the terms with the same power. For example 3x4 5x3 + 2x 4 + 2x3 + 2x2 + 4 = 3x4 3x3 + 2x2 + 2x. The degree of the sum is the maximum of the degrees of the two polynomials. 2 What to do Design an interface Polynomial that defines the above operations. This is your polynomial abstract data type. Specifically this interface should have the following method signatures: A method addTerm that takes a coefficient and a power (both integral numbers) and adds the resulting term to the polynomial. (This will enable you to build a polynomial term-by-term.) It should throw an illegalArgumentException if a negative power is passed to it. A method removeTerm that takes a power and removes any and all terms in the polynomial with that power. A method getDegree that returns the degree of this polynomial. A method get Coefficient that takes a power and returns the coefficient for the term with that power. A method evaluate that takes a double-precision decimal number and returns a double-precision result. A method add that takes another Polynomial object and returns the polynomial obtained by adding the two polynomials. Any implementation should ensure that this method does not mutate either polynomial. The implementation may assume that the given Polynomial is the of the same concrete class as this object; if it is a different class, the method may throw an IllegalArgumentException. Now implement this interface in a class PolynomialImpl. Beyond implementing the Polynomial interface, this implementation should have the following features/obey these constraints: This class should store the polynomial using the a linked list with nodes. This representation must be implemented by you (i.e. you are not allowed to use existing list classes in Java). This class should store only terms with non-zero coefficients. This class should store the polynomial terms in decreasing order of their powers. This class should have a constructor with no parameters that creates a polynomial with no terms, i.e. the polynomial o (how to represent this?). This class should have another constructor that takes a polynomial as a string, parses it and creates the polynomial accordingly. The string contains the polynomial, with each term separated by a space. The following examples should work with your constructor: O "4x^3 +3x^1 -5" o "-3x^4 - 2x^5 -5 +11x^1" Hint: Break the string into substrings and process. You may find the Scanner and String classes helpful to do this. Furthermore one can convert "23" into the integer 23 by using Integer.parseInt("23"). While you are free to write helper methods, you are not allowed to write any other public methods other than those in the interface and the above two constructors. This class should include a toString method that returns a string that contains the polynomial. The following examples should help you infer the required format: o 5x2 + 4x 2 creates the string 5x^2 +4x^1 -2 0 -50x3 + x2 + 3 creates the string -50x^3 +1x^2 +3 o 4x + 2x5 3x2 10 creates the string 2x^5 -3x^2 +4x^1 -10 Write tests that thoroughly test this implementation. As always, it is recommended to write the test before completing the PolynomialImpl implementation. 3 Hints: How to tackle the assignment Start by creating empty interfaces and classes for polynomials and nodes. Now select a method from the ADT and implement it end-to-end. Write tests for it before writing the implementation, and when your implementation passes your tests, move on to the next method. Tackle the parsing constructor at the end: you should not need it to test other methods. For the add method: think about how you can accumulate the result. This is just a hint: you do not need to implement it this way. Polynomials 1 Introduction A polynomial is made of several terms, each term having a coefficient and a variable raised to a power. Polynomials are one-variable if all their terms contain only one variable. An example of such a polynomial is f(x) = 3x4 5x3 + 2x 4. This polynomial has four terms. The degree of a polynomial is defined as the highest power of the variable in a term. In the above example, the degree of the polynomial is 4. The polynomials we deal with have only positive, integral powers. The coefficients of our polynomials are also integral numbers. Two polynomials are the same if they contain the same terms. Several algebraic operations are possible with polynomials. The simplest one is evaluating the polynomial for a specific value of the variable. For example, for a polynomial f(x) = 3x4 5x3 + 2x 4, its value at x = 2.5 is defined as f(2.5) = 3 * (2.5)4 5 * (2.5)3 + 2 + (2.5) 4 which is 40.0625. Polynomials can be added together to create a new polynomial. The addition is performed by combining all the terms and adding the coefficients of the terms with the same power. For example 3x4 5x3 + 2x 4 + 2x3 + 2x2 + 4 = 3x4 3x3 + 2x2 + 2x. The degree of the sum is the maximum of the degrees of the two polynomials. 2 What to do Design an interface Polynomial that defines the above operations. This is your polynomial abstract data type. Specifically this interface should have the following method signatures: A method addTerm that takes a coefficient and a power (both integral numbers) and adds the resulting term to the polynomial. (This will enable you to build a polynomial term-by-term.) It should throw an illegalArgumentException if a negative power is passed to it. A method removeTerm that takes a power and removes any and all terms in the polynomial with that power. A method getDegree that returns the degree of this polynomial. A method get Coefficient that takes a power and returns the coefficient for the term with that power. A method evaluate that takes a double-precision decimal number and returns a double-precision result. A method add that takes another Polynomial object and returns the polynomial obtained by adding the two polynomials. Any implementation should ensure that this method does not mutate either polynomial. The implementation may assume that the given Polynomial is the of the same concrete class as this object; if it is a different class, the method may throw an IllegalArgumentException. Now implement this interface in a class PolynomialImpl. Beyond implementing the Polynomial interface, this implementation should have the following features/obey these constraints: This class should store the polynomial using the a linked list with nodes. This representation must be implemented by you (i.e. you are not allowed to use existing list classes in Java). This class should store only terms with non-zero coefficients. This class should store the polynomial terms in decreasing order of their powers. This class should have a constructor with no parameters that creates a polynomial with no terms, i.e. the polynomial o (how to represent this?). This class should have another constructor that takes a polynomial as a string, parses it and creates the polynomial accordingly. The string contains the polynomial, with each term separated by a space. The following examples should work with your constructor: O "4x^3 +3x^1 -5" o "-3x^4 - 2x^5 -5 +11x^1" Hint: Break the string into substrings and process. You may find the Scanner and String classes helpful to do this. Furthermore one can convert "23" into the integer 23 by using Integer.parseInt("23"). While you are free to write helper methods, you are not allowed to write any other public methods other than those in the interface and the above two constructors. This class should include a toString method that returns a string that contains the polynomial. The following examples should help you infer the required format: o 5x2 + 4x 2 creates the string 5x^2 +4x^1 -2 0 -50x3 + x2 + 3 creates the string -50x^3 +1x^2 +3 o 4x + 2x5 3x2 10 creates the string 2x^5 -3x^2 +4x^1 -10 Write tests that thoroughly test this implementation. As always, it is recommended to write the test before completing the PolynomialImpl implementation. 3 Hints: How to tackle the assignment Start by creating empty interfaces and classes for polynomials and nodes. Now select a method from the ADT and implement it end-to-end. Write tests for it before writing the implementation, and when your implementation passes your tests, move on to the next method. Tackle the parsing constructor at the end: you should not need it to test other methods. For the add method: think about how you can accumulate the result. This is just a hint: you do not need to implement it this way
