4.10 Application-Based ADT Example
As a final example, we consider in this section an application-specific ADT that is representative of the relationship between application domains and the algorithms and data structures of the type that we consider in this book. The example that we shall consider is the polynomial ADT. It is drawn from symbolic mathematics, where we use the computer to help us manipulate abstract mathematical objects.
Our goal is to be able to write programs that can manipulate polynomials and perform computations such as
We also want to be able to evaluate the polynomial for a given value of x. For x = 0.5, both sides of this equation have the value 1.1328125. The operations of multiplying, adding, and evaluating polynomials are at the heart of a great many mathematical calculations.
The first step is to define the polynomial ADT, as illustrated in the interface Program 4.26. For a well-understood mathematical abstraction such as a polynomial, the specification is so clear as to be unspoken: We want instances of the ADT to behave precisely in the same manner as the well-understood mathematical abstraction. As for the ADT for complex numbers that we discussed in Section 4.8, our first preference might be to have a first-class ADT where we could use arithmetic operators such as * and + (which are well defined for polynomials), but Java does not support operator overloading, so we have to define standard methods. Just as we found for complex numbers, it is natural instead in Java to use an object-oriented approach where we define methods add and mult for any polynomial object to multiply itself by another polynomial.
Program 4.25 ADT interface for polynomials
This interface defines a polynomial ADT with integer coefficients. The constructor, when invoked with parameters c and N, is to create a polynomial corresponding to cxN.
class Poly // ADT interface { // implementations and private members hidden Poly(int, int) double eval(double) void add(Poly) void mult(Poly) public String toString() } Program 4.25 is a simple example of a client that performs the symbolic operations corresponding to the polynomial equations
and then evaluates the polynomial that results for a given value of x.
To implement the methods defined in the interface, we need to choose a particular data structure to represent polynomials and then to implement algorithms that manipulate the data structure to produce the behavior that client programs expect from the ADT. As usual, the choice of data structure affects the potential efficiency of the algorithms, and we are free to consider several. As with stacks and queues, we have the choice of using a linked representation or an array representation. Program 4.27 is an implementation using an array representation; the linked-list representation is left as an exercise (see Exercise 4.80).
To add two polynomials, we add their coefficients. If the polynomials are represented as arrays, the add method amounts to a single loop through the arrays, as shown in Program 4.27. To multiply two polynomials, we use the elementary algorithm based on the distribu-tive law. We multiply one polynomial by each term in the other, line up the results so that powers of x match, then add the terms to get the final result. The following table summarizes the computation for 
Program 4.26 Polynomial client (binomial coefficients)
This client program uses the polynomial ADT that is defined in the interface Program 4.26 to perform algebraic manipulations on polynomials with integer coefficients. It takes an integer N and a floating-point number p from the command line, computes (x + 1)N, and checks the result by evaluating the resulting polynomial at x = p.
public class Binomial { public static void main(String[] args) { int N = Integer.parseInt(args[0]); double p = Double.parseDouble(args[1]); Poly y = new Poly(1, 0); Poly t = new Poly(1, 0); t.add(new Poly(1, 1)); for (int i = 0; i < N; i++) { y.mult(t); Out.println(y + ""); } Out.println("value: " + y.eval(p)); } } 
The computation seems to require time proportional to N2 to multiply two polynomials. Finding a faster algorithm for this task is a significant challenge. We shall consider this topic in detail in Part 8, where we shall see that it is possible to accomplish the task in time proportional to N3/2 using a divide-and-conquer algorithm, and in time proportional to N lg N using the fast Fourier transform.
The implementation of the evaluate method in Program 4.27 uses a classic efficient algorithm known as Horner's algorithm. A naive implementation of the method involves a direct computation using a method that computes xN. This approach takes quadratic time. A less naive implementation involves saving the values of xi in a table, then using them in a direct computation. This approach takes linear extra space. Horner's algorithm is a direct optimal linear algorithm based on parenthesizations such as
Horner's method is often presented as a time-saving trick, but it is actually an early and outstanding example of an elegant and efficient algorithm, which reduces the time required for this essential computational task from quadratic to linear. The calculation that we performed in Program 4.5 for converting ASCII strings to integers is a version of Horner's algorithm. We shall encounter Horner's algorithm again, in Chapter 14 and Part 5, as the basis for an important computation related to certain symbol-table and string-search implementations.
The add and mult operators construct new arrays to hold their results. We overwrite references to the old ones leaving a (potentially huge) number of objects with no references to them. We depend upon the Java garbage-collection mechanism to reclaim the memory associated with these objects (see Exercise 4.79). Because we have to create new objects anyway, the use of static methods instead of class methods is a reasonable alternative for this application (see Exercise 4.78).
As usual, the array representation for implementing the polynomial ADT is but one possibility. If exponents are huge and there are not many terms, a linked-list representation might be more appropriate (see Exercise 4.80). For example, we might not want to use Program 4.27 to perform a multiplication such as
because it would use an array with space for millions of unused coefficients while a linked-list implementation would only use a few nodes.
Program 4.27 Array implementation of polynomial ADT
In this implementation of an ADT for polynomials, the data representation consists of the degree and a pointer to an array of coefficients.
class Poly { private int n; private int[] a; Poly(int c, int N) { a = new int[N+1]; n = N+1; a[N] = c; for (int i = 0; i < N; i++) a[i] = 0; } double eval(double d) { double t = 0.0; for (int i = n-1; i >= 0; i--) t = t*d + (double) a[i]; return t; } void add(Poly p) { int[] t = new int[(p.n > n) ? p.n : n]; for (int i = 0; i < p.n; i++) t[i] = p.a[i]; for (int j = 0; j < n; j++) t[j] += a[j]; a = t; n = t.length; } void mult(Poly p) { int[] t = new int[p.n + n -1]; for (int i = 0; i < p.n; i++) for (int j = 0; j < n; j++) t[i+j] += p.a[i] * a[j]; a = t; n = t.length; } public String toString() { String s = ""; for (int i = 0; i < n; i++) s += a[i] + " "; return s; } } Exercises
4.78 Develop a version of the Poly class in this section (Program 4.27) that uses static methods instead of class methods for add and mult, and write a version of the binomial-coefficients client (Program 4.25) that uses your class.
4.79 Compare the performance of your solution to Exercise 4.62 with the programs in the text, by removing the println statements and comparing running times for N = 100, 1000, and 10000.
4.83 Modify your polynomial ADT from Exercise 4.82 to ignore all terms with exponents greater than or equal to an integer M, which is provided by the client at initialization.
4.84 Extend your polynomial ADT from Exercise 4.82 to include polynomial division and composition.
4.88 Develop an ADT that provides clients with the ability to perform algebraic operations on vectors of floating-point numbers.
4.89 Develop an ADT that provides clients with the ability to perform algebraic operations on matrices of abstract objects for which addition, subtraction, multiplication, and division are defined.
4.90 Write an interface for a character-string ADT, which includes operations for creating a string, comparing two strings, concatenating two strings, copying one string to another, and returning the string length. Note: Your interface will be quite similar to the interface provided for the standard Java String type.
4.91 Provide an adapter class that implements your string ADT interface from Exercise 4.90, using the standard Java String type where appropriate.
4.92 Provide an implementation for your string interface from Exercise 4.90, using a linked list for the underlying representation. Analyze the worst-case running time of each operation.
4.93 Write an interface and an implementation for an index set ADT, which processes sets of integers in the range 0 to M - 1 (where M is a defined constant) and includes operations for creating a set, computing the union of two sets, computing the intersection of two sets, computing the complement of a set, computing the difference of two sets, and printing out the contents of a set. In your implementation, use an array of M - 1 boolean values to represent each set.
4.94 Write a client program that exercises your ADT from Exercise 4.93.
| Top |
EAN: 2147483647
Pages: 158