could you please help me implement this class, i can provide the required information and a python script and also have linklistPolynomials and Linked lists

Polynomial class

You are to implement a Polynomial class that supports an integer polynomial datatype. Quite often, such a datatype can be implemented using a list or an array. However, our Polynomials will be sparse, meaning that a lot of terms will be zero. In such a case, only the nonzero terms should be stored in the data structure. For this assignment, you must use a linked list to store the nonzero terms of the polynomial.

Your solution must adhere to the following specification:

$1$

$.$

$$Polynomials can be created with an optional list of tuples where a tuple represents a

$($

coefficient

$,$

$$exponent

$)$

$$pair$.$

For example, Polynomial

$([(1$

$,$

$0)$

$,$

$(3$

$,$

$3)$

$,$

$(2$

$,$

$1)])$

$$represents

$3$

x

$^$

$3$

$+$

$2$

x

$+$

$1$

$.$

$$Any combination of tuples can be used to represent a polynomial. Exponents can appear more than once, and coefficients can be zero. You must collect like terms and remove all terms that are zero. Terms must be stored in descending order of exponent. Polynomials must be stored in a unique or canonical form. Polynomial

$()$

$$with no argument creates a zero polynomial

$0$

x

$^$

$0$

$.$

$2$

$.$

$$The Polynomial class must implement a

$\_$

$\_$

str

$\_$

$\_$

$()$

$$method that returns a string

representation of a Polynomial object so that it can be printed. A polynomial must be printed in its stored canonical form, i

$.$

e

$.$

$,$

$$in descending order of exponent with no zero terms or coefficients of

$1$

$.$

$$For the zero polynomial, this method should return

$"0"$

$.$

$3$

$.$

$$You are to provide the methods iszero

$()$

$,$

$$eval

$($

a

$)$

$,$

$$degree

$()$

$,$

and lowest

$\_$

term

$()$

$.$

$$The iszero

$()$

$$method returns a Boolean that reports whether the polynomial is the zero polynomial. The eval

$($

a

$)$

$$method returns the evaluation of the polynomial at x

$=$

a

$.$

$$The degree

$()$

$$method returns the degree of the polynomial; for simplicity, return

$0$

$$for the zero polynomial.

$($

Strictly speaking, the degree of the zero polynomial is undefined.

$)$

$.$

$$The lowest

$\_$

term

$()$

$$method returns the exponent of the lowest non

$-$

zero term.

$4$

$.$

$$You are to provide the method horners

$()$

$$that will return a string of the Horner

$$

s rule representation of the polynomial. The Horner

$$

s rule representation of the polynomial anxn

$+$

$$an

$-$

$1$

xn

$-$

$1$

$+$

$.$

$.$

$.$

$.$

$+$

$$a

$1$

x

$+$

$$a

$0$

$$is the string

$"$

x

$($

x

$($

$.$

$.$

$.$

$($

x

$($

anx

$+$

$$an

$-$

$1)$

$+$

$$an

$-$

$2)$

$+$

$.$

$.$

$.$

$)$

$+$

a

$0"$

$.$

$$Zero terms and a coefficient an of

$1$

$$must not be included in the return string. For example, for the polynomial

$-$

x

$^$

$4$

$+$

$3$

x

$^$

$2$

$+$

$5$

$,$

$$the method should return the string

$"$

x

$($

x

$($

x

$($

$-$

x

$)$

$+$

$3))$

$+$

$5"$

$.$

$5$

$.$

$$There are additional requirements on the time and extra space costs of the methods above that you must adhere to as shown in the table below. Extra space cost does not include the input. Below, n is the degree of the polynomial.

Method Time Cost Extra Space Cost

iszero O

$(1)$

$$ O

$(1)$

eval O

$($

n

$)$

$$ O

$(1)$

degree O

$(1)$

$$ O

$(1)$

lowest

$\_$

term O

$($

n

$)$

$$ O

$(1)$

horners O

$($

n

$)$

$$ O

$($

n

$)$

: constant space andspace for the string returned

str O

$($

n

$)$

$$ O

$($

n

$)$

: constant space and space for the string returned

$6$

$.$

$$You must override the

$+$

$$and

$*$

$$operators

$($

$\_$

$\_$

add

$\_$

$\_$

$$and

$\_$

$\_$

mul

$\_$

$\_$

$)$

$$so that the Polynomial class supports polynomial addition and multiplication. Each method should return the addition or multiplication result as a new polynomial instead of modifying the operands.

You should make use of isinstance

$()$

$$to verify that the second operand is valid

$($

i

$.$

e

$.$

$,$

$$a polynomial

$)$

$.$

$$If it isn

$$

t valid, then return None.

Note: Please feel free to create an additional helper class to implement the Polynomial class.

For example, creating a Term class could help represent a single term in a polynomial and is considered good style.

Grading Criteria:

$10$

$$marks

$$

$$Milestone

$1$

: In the second lab period, you will demo to your instructor the constructor and the string method of both the Term and the Polynomial classes. Your methods must adhere to the requirements. Your instructor will provide more details if needed.