Quiz 9, 10/25


Let n and k be positive integers such that n >= k. The number of ways of choosing k objects out of n, is denoted by C(n, k). C(n, k) is called a binomial coefficient and is sometimes read as "n choose k." For example, two objects can be chosen from the set {1, 2, 3, 4} as follows: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, and {3, 4}. Thus C(4, 2) is 6.

There are a number of well known recurrences for binomial coefficients. Here is the most well known:

C(n, k) = C(n-1, k) + C(n-1, k-1).

Note that C(n, 1) = n (one object can be chosen from n in exactly n ways), C(n, 0) = 1 (0 objects can be chosen from n in exactly 1 way), and C(n, n) = 1 (n objects can be chosen from n in exactly 1 way). The above recurrence can be used to implement a simple, recursive function to compute C(n, k), for any given n and k. Here is this function:

        public static int binomial(int n, int k)
        {
                if(n < k)
                        return 0;

                if((n == k) || (k == 0))
                        return 1;

                if(k == 1)
                        return n;

                return binomial(n-1, k) + binomial(n-1, k-1);
        }

This implementation is correct, but it suffers from the same efficiency problem that the standard, recursive Fibonacci numbers program suffers from. As in the case of the Fibonacci number function, the function binomial can be enormously speeded up if old answers are remembered. In order to remember old answers, start with a 2-dimensional integer table of answers initialized to -1; as each binomial coefficient C(i, j) is computed, it is stored in slot [i][j]. When a binomial coefficient C(i, j) needs to be computed, the function first looks up the answers table to see if C(i, j) has already been computed and computes it only if the answers table does not have a value for C(i, j), already.

Implement a fastBinomial function using the ideas mentioned in the above paragraph. Use this method to compute C(500, 250). Note that just like in FastFibonacci.java you will need to use the BigInteger class to avoid integer overflow problems.