The Polynomial ADT

The Polynomial ADT (HSM Ch.2.3)
- What is a polynomial?
- A polynomial object is a homogeneous ordered list of pairs <exponent,coefficient>, where each coefficient is unique.
- Operations include returning the degree, extracting the coefficient for a given exponent, addition, multiplication, evaluation for a given input.
Representation of Polynomials (HSM Ch.2.3.1)
- Fixed maximal degree
  - Representation (HSM Ch.2.3.1, Representation 1)
  - Wastes space if maximal polynomial degree is less than maximal possible degree.
- Dynamic degree
  - Representation (HSM Ch.2.3.1, Representation 2)
  - Wastes space if polynomial is sparse.
- Sparse polynomials, global storage
  - Representation (HSM Ch.2.3.1, Representation 3)
  - Limited number of total polynomial terms.
- Sparse polynomials, local storage (HSM Ch.2.3.3)
  - Representation
    - slpolynomialclass.h
  - Have to compute size before creation. Hard work to add new terms.
Polynomial Addition (HSM Ch.2.3.2)
- Using sparse polynomials, global storage
  - Algorithm (HSM Program 2.8)
  - Complexity
- Using sparse polynomials, local storage
  - Algorithm
  - Complexity
    - Twice as long?
    - Does it matter?

Exercises

Define the polynomial ADT.
Describe how an array can be effectively used to store a non-sparse polynomial of known degree, so that the access time to the term for a given exponent is O(1).
Describe how a sparse polynomial may be space-efficiently stored using an array.
Give an algorithm for adding two sparse polynomials stored in arrays of fixed size. What is the asymptotic complexity of the algorithm?
Give an algorithm for adding two sparse polynomials stored in arrays whos size is determined by the number of terms in the polynomial. What is the asymptotic complexity of the algorithm?