Task 7.1 - Polynomials Data Structure

A polynomial such as p(x) = 5 x^11^ + 3 x^3^ + 6x + 1 forms an essential mathematical entity useful in many applications. A polynomial in general is a sum of terms of the form a_n * x^n where a_n is the coefficient of the term of order n. The purpose of this lab task is to develop an abstract data type which can represent such polynomials of arbitrary degree (largest order of its term) and finitely many non-zero coefficients. You may assume the coefficients are constants (doubles), and not variables, and only constant, positive integer degrees are allowed.

  • Implement a class data structure that can represent a polynomial of the above type. Decide upon the storage format (representation) for a polynomial such that the operations below are supported efficiently. Implement all non-simple data types you need for the representation yourself and do not use the data types from any the Java API.

The class should offer methods for the operations below. You should also implement tests for these methods (e.g. using your own test framework or possibly JUnit) and find the most efficient representation and implementation assuming that all the operations are executed equally likely.

  • Create a zero polynomial (p(x) = 0) in the constructor.
  • Set the coefficient of a term of arbitrary order (incl. setting it to 0 which removes the term).
  • Get the coefficient of a term of some given order.
  • Output the polynomial to a given PrintStream.
  • Add two polynomials to give a new one (e.g. the sum of p(x) = 5x^33^ + 3x^2^ + 5x and q(x) = 7x^2^ + 3 is p(x) + q(x) = 5x^33^ + 10x^2^ + 5x + 3).
  • Subtract two polynomials to give a new one (e.g. with the ploynomials above p(x) - q(x) = 5x^33^ - 4x^2^ + 5x - 3).
  • Multiply two polynomials (e.g. with the polynomials above p(x) * q(x) = (5x^33^ + 3x^2^ + 5x) * (7x^2^ + 3) = 35x^35^ + 15x^33^ + 21x^4^ + 35x^3^ + 9x^2^ + 15x).

Optionally you may try to extend the functionality of the data type by methods such as

  • Compute the integral (\int p(x) dx) of a polynomial.
  • Compute the derivative (dp(x) / dx) of a polynomial.
  • Divide one polynomial by another (see Euclidean division, division with remainder or polynomial long division).
  • Find one (or all!?) roots of the polynomial, i.e. solve p(x) = 0.
  • Other useful operations you can think of.