Polynomial Operations Solution

Introduction




You learned in a college algebra or calculus course that a polynomial, ( ), in one variable, , is an expression of the form:

( ) = 0 + 1 + ⋯ +




where are real (or complex) numbers and is a non-negative integer. If ( ) = 0, then ( ) is called a constant polynomial. If ( ) is a non-zero constant polynomial, the degree of ( ) is defined to be 0.




Even though, in mathematics, the degree of the zero polynomial is undefined, for the purpose of this program, we consider the degree of such polynomials to be zero. If ( ) is not constant and ≠ 0, then is called the degree of ( ), that is, the degree of a non-constant polynomial is defined to be the

exponent of the highest power of .




The basic operations performed on polynomials are add, subtract, multiply, divide, and evaluate a polynomial at a given point. For example, suppose that

( ) = 1 + 2 + 3 4

and

( ) = 4 + 2

The degree of ( ) is 4 and the degree of ( ) is 2. Moreover, (2) = 1 + 2 ∙ 2 + 3 ∙ 24 = 53




( ) + ( ) = (1 + 4) + (2 + 0) + (0 + 1) 2 + (0 + 0) 3 + (3 + 0) 4 = 5 + 2 + 2 + 3 4 ( ) − ( ) = (1 − 4) + (2 − 0) + (0 − 1) 2 + (0 − 0) 3 + (3 − 0) 4 = −3 + 2 − 2 + 3 4 ( ) × ( ) = (4 × 1) + (4 × 2) + (1 × 1) 2 + (2 × 1) 3 + (3 × 1) 6 = 4 + 8 + 2 + 2 3 + 3 6




Next, we define the basic operations performed on polynomials, namely addition, subtraction, and multiplication. Suppose that ( ) and ( ) are the following polynomials:

( ) = + + ⋯ + − − +

( ) = + + ⋯ + − − +

Let = ⁡(⁡ , ). Then

( ) + ( ) = + + ⋯ + − − +

where, for = , , , ⋯ , ,

+ ⁡⁡⁡ ⁡ ≤ ⁡( , )

= { ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ ⁡

⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡ ⁡




The difference, ( ) − ( ), of ( ) and ( ) can be defined similarly. It follows that the degree of the polynomials is less than or equal to ⁡(⁡ , ).

The product, ( ) × ( ), of ( ) and ( ) is defined as follows:

( ) × ( ) = + + ⋯ + + +

The coefficient , for = , , , ⋯ , + , is given by the formula = ∙ + ∙ − + ⋯ + ∙ where is either or does not exist, it is assumed to be zero. For example, = , = + and so on + = .




Problem Statement




The purpose of this programming assignment is to design and implement the class Polynomials.java to perform the various polynomial operations in a program. To be specific, this program implements the following operations on polynomials.




Evaluate a polynomial at a given value.
Add two polynomials.
Subtract two polynomials.
Note:




Design Requirements




It is assumed that the coefficients of polynomials are integers.




To store a polynomial, your program must use the ABList.java class developed in class.




A traditional array-based list representation of a polynomial is to use one array element to only




represent the coefficient of one term. You may take advantage of the fact that array elements indices are integer values ranging from 0 to and could be thought of as the exponents of the variable. For example, here is how polynomials ( ) and ( ) can be represented:




0
1


2
3
4
1


2


0
0
3


0




1




2


4




1




0



The terms of a polynomial can be stored in an increasing or in a decreasing order of exponent.




Program Input




The program gets its input from a data file named polynomials.txt with data organized as follows:




The first line in the input file contains only one integer representing the value of to be used to evaluate the two polynomials.




Each remaining line in the input file represents a polynomial and contains an even number of integers.




Each term in a polynomial is represented using a pair of integers. The components of the pair are separated by a single blank.




The first component in a pair represents the coefficient and the second component represents the power.

Here is a sample input file for the example polynomials ( ) and ( ) of the Introduction section:

−1

1⁡0⁡2⁡1⁡0⁡2⁡0⁡3⁡3⁡4

4⁡0⁡0⁡1⁡1⁡2




Program Output




Your program should begin by displaying the two input polynomials (see format below). Your program then adds and subtracts the two polynomials displaying the resulting polynomial from each operation. Your program then ends by evaluating each input polynomial at the given value of , and displaying the result. Below is a sample output based on the sample input provided above.

Program is reading input file to obtain the two polynomials. The two input polynomials are:

p(x) = (1 + 2x + 3x^4)




q(x) = (4 + x^2)




Program is now performing arithmetic operations on the two polynomials…

(1 + 2x + 3x^4) + (4 + x^2) = (5 + 2x + x^2 + 3x^4)




(1 + 2x + 3x^4) - (4 + x^2) = (-3 + 2x – x^2 + 3x^4)




Program is now evaluating each polynomial using x = -1

p(-1) = 2




q(-1) = 5




Program is done.




Bye!




Extra Credit Opportunity




If you would like to challenge yourself and get bonus credit, you may want to consider the following:




Use a linked-list to represent a polynomial since it is more efficient and uses less computer memory. Here is how polynomials p(x) and q(x) can be represented using a linked list:







firstNode




















lastNode






























































































1












2












3




































































































0












1












4




































































































































































































firstNode






lastNode
































































































4












1










































0












2










































































Add an operation to multiply two polynomials.







Submission Instructions




When you are satisfied with your implementation, and after testing it thoroughly, submit the Polynomials.java file via Blackboard Learn.































Page 3 of 3