Saturday, November 29, 2014

Polynomial ADT - Array Implementation



What is Polynomial ?

A polynomial is a mathematical expression consisting of a sum of terms, each term including a variable or variables raised to a power  and multiplied by a coefficient.  The simplest polynomials have one variable.  A one-variable (uni-variate) polynomial of degree n has the following form:


A Polynomial is can be expressed in terms that only have positive integer exponents and the operations of addition, subtraction, and multiplication. In other words, it must be possible to write the expression without division. It's easiest to understand what makes something a polynomial equation by looking at examples and non examples as shown below.



  • 3x2 + 5x +100 --> Since all of the variables have integer exponents that are positive this is a polynomial.
  • 10x +1            --> Since all of the variables have integer exponents that are positive this is a polynomial.
  • (5x9 + 5x7 - 10) * 2x --> Since all of the variables have integer exponents that are positive this is a polynomial.
  • 9x-5 +6          --> Not a polynomial because a term has a negative exponent.
  • 7x½ +3          --> Not a polynomial because a term has a fraction exponent.

Degree of a Polynomial::

The degree is the value of the greatest exponent of any expression (except the constant ) in the polynomial. To find the degree all that you have to do is find the largest exponent in the polynomial.


  • 3x2 + 5x +100 --> Degree is 2
  • 10x +1           -->  Degree is 1
  • 5x9 + 5x7 - 10 --> Degree is 9

Polynomial Addition::



Polynomial Subtraction::




Polynomial Multiplication::



Polynomial Structure Implementation::


Zero Polynomial::


Add Polynomial::





Polynomial Multiplication::





Advantages of Array Implementation:

  • ease of storage and retrieval.
  • only good for non-sparse polynomials.

Disadvantages of Array Implementation::


  • have to allocate array size ahead of time.
  • huge array size required for sparse polynomials. Waste of space and runtime.

Reference::

  Data Structure and Algorithm Analysis in C, 2nd Edition, Mark Allen Weiss

Goto Data Structure Concepts

No comments:

Post a Comment