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

Example-Computing Binomial Coefficients


Consider the problem of computing the binomial coefficient


given non-negative integers n and m (see Theorem gif).

The problem with implementing directly Equation gif is that the factorials grow quickly with increasing n and m. For example, tex2html_wrap_inline68016. Therefore, it is not possible to represent n! for tex2html_wrap_inline68020 using 32-bit integers. Nevertheless it is possible to represent the binomial coefficients tex2html_wrap_inline68022 up to n=33 without overflowing. For example, tex2html_wrap_inline68026.

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 gif directly as a recursive method, we get a method whose running time is given by


which is very similar to Equation gif. In fact, we can show that tex2html_wrap_inline68028 which (by Equation gif) 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 tex2html_wrap_inline67988 from the information contained in tex2html_wrap_inline66813 simply by using Equation gif. Table gif shows the sequence in tabular form--the tex2html_wrap_inline57621 row of the table corresponds the sequence tex2html_wrap_inline66813. This tabular representation of the binomial coefficients is known as Pascal's triangle .gif



n tex2html_wrap_inline68040 tex2html_wrap_inline68042 tex2html_wrap_inline68044 tex2html_wrap_inline68046 tex2html_wrap_inline68048 tex2html_wrap_inline68050 tex2html_wrap_inline68052 tex2html_wrap_inline68054
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
Table: Pascal's triangle.

Program gif defines the method Binom which takes two integer arguments n and m and computes the binomial coefficient tex2html_wrap_inline68022 by computing Pascal's triangle. According to Equation gif, 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 tex2html_wrap_inline58403, 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 tex2html_wrap_inline67988 are computed in reverse so that they can be written over the elements of tex2html_wrap_inline66813 that are no longer needed.

Program: Dynamic programming example--computing Binomial coefficients.

The worst-case running time of the Binom method given in Program gif is clearly tex2html_wrap_inline58403.

next up previous contents index

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