Text version: Computing the number of combinations of size k of a set of n items C(n, k) = n choose k , where n choose k = n! /(nk)!k! on a computer can be awkward. Computing the numerator and denominator separately and then dividing tends to overflow the integer representation for the intermediate calculations; on the other hand, computing the overall result as the product of floating-point ratios n k n1 k1 . . . nk+1 1 can introduce rounding errors. To get a correct integer answer without over owing, we can use Pascals Formula, which defines the number of combinations using the following recurrence:

C(i, j) = 1 if j = 0 or i = j

C(i 1, j 1) + C(i 1, j) if 1 j i 1

The recurrence is undefined if j > i, or if either i or j is negative. Design and write a dynamic programming algorithm based on the above recurrence that will compute n k given n and

Question 2 (6 marks) Computing the number of combinations of size k of a set of n items C(n, k)(), where on a computer can be awkward. Computing the numerator and denominator separately and then dividing tends to overflow the integer representation for the intermediate calculations; on the other hand, computing the overall result as the product of floating-point ratios 1k+1 can introduce rounding errors To get a correct integer answer without over owing, we can use Pascal's Formula, which defines the number of combinations using the following recurrence: C(i -1,j -1) + C(i-1,j) if 1 Sj Si-1 The recurrence is undefined if j > i, or if either i or j is negative. Design and write a dynamic programming algorithm based on the above recurrence that will compute (?) given n and k