Data Structures and Algorithms
with Object-Oriented Design Patterns in C#|
Consider the problem of computing the binomial coefficient
given non-negative integers n and m (see Theorem ).
The problem with implementing directly Equation is that the factorials grow quickly with increasing n and m. For example, . Therefore, it is not possible to represent n! for using 32-bit integers. Nevertheless it is possible to represent the binomial coefficients up to n=33 without overflowing. For example, .
Consider the following recursive definition of the binomial coefficients:
This formulation does not require the computation of factorials. In fact, the only computation needed is addition.
If we implement Equation directly as a recursive method, we get a method whose running time is given by
which is very similar to Equation . In fact, we can show that which (by Equation ) is not a very good running time at all! Again the problem with the direct recursive implementation is that it does far more work than is needed because it solves the same subproblem many times.
An alternative to the top-down recursive implementation is to do the calculation from the bottom up. In order to do this we compute the series of sequences
Notice that we can compute from the information contained in simply by using Equation . Table shows the sequence in tabular form--the row of the table corresponds the sequence . This tabular representation of the binomial coefficients is known as Pascal's triangle .
Program defines the method Binom which takes two integer arguments n and m and computes the binomial coefficient by computing Pascal's triangle. According to Equation , each subsequent row depends only on the preceding row--it is only necessary to keep track of one row of data. The implementation shown uses an array of length n to represent a row of Pascal's triangle. Consequently, instead of a table of size , the algorithm gets by with O(n) space. The implementation has been coded carefully so that the computation can be done in place. That is, the elements of are computed in reverse so that they can be written over the elements of that are no longer needed.
Program: Dynamic programming example--computing Binomial coefficients.
The worst-case running time of the Binom method given in Program is clearly .