Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index



The applications of lists and ordered lists are myriad. In this section we will consider only one--the use of an ordered list to represent a polynomial. In general, an tex2html_wrap_inline57687-order polynomial in x, for non-negative integer n, has the form


where tex2html_wrap_inline60991. The term tex2html_wrap_inline57623 is the coefficient of the tex2html_wrap_inline57621 power of x. We shall assume that the coefficients are real numbers.

An alternative representation for such a polynomial consists of a sequence of ordered pairs:


Each ordered pair, tex2html_wrap_inline60999, corresponds to the term tex2html_wrap_inline61001 of the polynomial. That is, the ordered pair is comprised of the coefficient of the tex2html_wrap_inline57621 term together with the subscript of that term, i. For example, the polynomial tex2html_wrap_inline61007 can be represented by the sequence tex2html_wrap_inline61009.

Consider now the tex2html_wrap_inline61011-order polynomial tex2html_wrap_inline61013. Clearly, there are only two nonzero coefficients: tex2html_wrap_inline61015 and tex2html_wrap_inline61017. The advantage of using the sequence of ordered pairs to represent such a polynomial is that we can omit from the sequence those pairs that have a zero coefficient. We represent the polynomial tex2html_wrap_inline61013 by the sequence tex2html_wrap_inline61021

Now that we have a way to represent polynomials, we can consider various operations on them. For example, consider the polynomial


We can compute its derivative  with respect to x by differentiating  each of the terms to get


where tex2html_wrap_inline61025. In terms of the corresponding sequences, if p(x) is represented by the sequence


then its derivative is the sequence


This result suggests a very simple algorithm to differentiate a polynomial which is represented by a sequence of ordered pairs:

  1. Drop the ordered pair that has a zero exponent.
  2. For every other ordered pair, multiply the coefficient by the exponent, and then subtract one from the exponent.
Since the representation of an tex2html_wrap_inline57687-order polynomial has at most n+1 ordered pairs, and since a constant amount of work is necessary for each ordered pair, this is inherently an tex2html_wrap_inline59919 algorithm.

Of course, the worst-case running time of the polynomial differentiation will depend on the way that the sequence of ordered pairs is implemented. We will now consider an implementation that makes use of the OrderedListAsLinkedList class. To begin with, we need a class to represent the terms of the polynomial. Program gif gives the definition of the Term class and several of its methods.

Program: Term class.

Each Term instance has two fields, coefficient and exponent, which correspond to the elements of the ordered pair as discussed above. The former is a double and the latter, an int.

The Term class extends the ComparableObject class introduced in Program gif. Therefore, instances of the Term class may be put into a container. Program gif defines three methods: a constructor, CompareTo, and Differentiate. The constructor simply takes a pair of arguments and initializes the corresponding fields accordingly.

The CompareTo method is used to compare two Term instances. Consider two terms , tex2html_wrap_inline61035 and tex2html_wrap_inline61037. We define the relation tex2html_wrap_inline61039 on terms of a polynomial as follows:


Note that the relation tex2html_wrap_inline61039 does not depend on the value of the variable x. The CompareTo method implements the tex2html_wrap_inline61039 relation.

Finally, the Differentiate method does what its name says: It differentiates a term with respect to x. Given a term such as tex2html_wrap_inline61049, it computes the result (0,0); and given a term such as tex2html_wrap_inline60999 where i>0, it computes the result tex2html_wrap_inline61057.

We now consider the representation of a polynomial. Program gif defines the Polynomial abstract class. The class comprises three abstract methods--Add, Differentiate, and Plus. The Add method is used to add terms to a polynomial. The Differentiate method differentiates the polynomial. The Plus method is used to compute the sum of two polynomials. In addition to these methods, the addition operator + is overloaded for Polynomial operands.

Program: Polynomial abstract class.

Program gif introduces the PolynomialAsOrderedList class. This concrete class implements the Polynomial interface. It has a single field of type OrderedList. In this case, an instance of the OrderedListAsLinkedList class is used to contain the terms of the polynomial.

Program: PolynomialAsOrderedList class.

Program gif defines the method Differentiate which has the effect of changing the polynomial to its derivative with respect to x. To compute this derivative, it is necessary to call the Differentiate method of the Term class for each term in the polynomial. Since the polynomial is implemented as a container, there is an Accept method which can be used to perform a given operation on all of the objects in that container. In this case, we define a visitor, DifferentiatingVisitor, which assumes its argument is an instance of the Term class and differentiates it.

After the terms in the polynomial have been differentiated, it is necessary to check for the term (0,0) which arises from differentiating tex2html_wrap_inline61049. The Find method is used to locate the term, and if one is found the Withdraw method is used to remove it.

The analysis of the running time of the polynomial Differentiate method is straightforward. The running time required to differentiate a term is clearly O(1). So too is the running time of the Visit method of the DifferentiatingVisitor. The latter method is called once for each contained object. In the worst case, given an tex2html_wrap_inline57687-order polynomial, there are n+1 terms. Therefore, the time required to differentiate the terms is O(n). Locating the zero term is O(n) in the worst case, and so too is deleting it. Therefore, the total running time required to differentiate a tex2html_wrap_inline57687-order polynomial is O(n).

next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.