Design and write a Dynamic Programming Algorithm!

Note that, even though desired running times are not specified, faster algorithms are better and thus worth more marks. 1. Computing the number of combinations of size k of a set of n items (C(n, k), where d "(n, k) = na!TR) 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 ( .....- !) can introduce rounding errors. To get a correct integer answer without overflowing, we can use Pascal's Formula, which defines the number of combinations using the following recurrence: if j 0 or i-j C(i,j) = Ci-1,j-1) +Ci- 1,j) if 1 sjsi- 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 C(n, k), given n and k