Linked lists are a convenient way to represent polynomials | Complete Solution

Task

Assessment 2 has total 40 marks. Marks will be scaled according to the value of the assignment.

Linked lists are a convenient way to represent polynomials. Your task is to design a program that does some polynomial operations using a linked list.

A polynomial of degree 𝑚 is defined as,

a₀x^m+a₁x^m−1+...+ a_m−1x¹+a_m 

The degree 𝑚 is the largest exponent in any of the terms of the polynomial. For example, the largest exponent in 4x²−7x+3 is 2.

It is customary to write the term with the largest exponent first, followed by the term with the next largest exponent and so on.

a_i s are the coefficients of the polynomial. One example of a polynomial of degree 6 is

2x⁶+x³+5x+4

in which the first term's coefficient is a₀=2 and its power is 6; the second term's coefficient is a₁=1 and its power is 3.

Tasks are detailed as follows

• You are required to develop your own class to represent polynomials as a linked list. The first node in the list represents the first term in the polynomial, the second node represents the second term, and so forth.
• Each node contains three fields. The first field is the term's coefficient. The second field is the term's power, and the third field is a pointer to the next term.
• The following examples show how a polynomial is represented as a linked list.

5x⁴+6x³+7

2x³−7x²+3x

Notice that in the linked list:

1.      The list has as many nodes as there are terms in the polynomial.

2.      Each node in the linked list contains a value for the coefficient, a value for the exponent and a reference.

3.      The nodes in the linked list are ordered. Nodes with a higher exponent precede nodes with a lower exponent.

4.      The constant term has an exponent of 0.

5.      The reference of the last node is NULL.

What to Implement (Task):

• You should have at least two constructor for polynomials. One is used to build a polynomial (linked list) from a file and the other from keyboard input (pairs of coefficients and powers) by a user.
• Implement polynomial addition by using an add() method, so you could write in program :

PolynomialThree= PolynomialOne.add(PolynomialTwo);

The rules for the addition of polynomials are as follows:

1. If the powers are equal, the coefficients are algebraically added.

2. If the powers are unequal, the term with the higher power is inserted in the new polynomial.

3. If the exponent is 0, it represents x0, which is 1. The value of the term is therefore the value of the coefficient.

4. If the result of adding the coefficients results in 0, the term is dropped (0 times anything is 0).

For example, the polynomial sum (27x³+15x²+12x)+(18x²+10x+8)is calculated as

27x³+33x²+22x+8

• Get the value of a polynomial given an input. For instance, given x=2, the value of the polynomial x²+3x+2 is 12 .
• Implement the product of a polynomial by another polynomial which is the algebraic sum of the products of one polynomial by all the monomials of another polynomial.
• Implement the derivative operation for a polynomial. Note that for a monomial ax^k, its derivative is kax^{k -1}and the derivative of a constant is 0 and the derivative of a polynomial is equal to the sum of derivatives of its all monomials.
• Implement a InsertTerm() method. This method should put the input term into a polynomial.
• Test your program with the following two polynomials

12x⁹+5x⁶+13x⁵−4x⁴+2x³+11x² - 6

7x⁹+2x⁸+5x⁶+2x⁵+2x³+9x² - 7x

• Write a driver program to test all the functionalities that you have defined