Algorithms Problem

7. Binomial Coefficients. 15 marks; 5 marks each You may recall that the binomial coefficient, denoted C(n, k) or is the number of combinations (subsets) of k elements from an n-element set (0 S k S n). The name "binomial coefficients" comes from the participation of these numbers in the binomial formula: m, n Of the numerous properties of binomial coefficients, we focus on two: C(n, k) O(n 1, 1) C(n 1, k) for n k 0, for all integers n -0 C n, 0) C(n,n) 1 for all integers n 0 (a) Give pseudocode for a dynamic programming algorithm to compute C n, k) that uses only addi- tions. [5 marks (b) What is the time and space efficiency of your algorithm? 5 marks (c) Find the exact number of additions made by your algorithm, i.e set up an expression A(n, k) counting the total number of additions made by your algorithm in computing C(n, k) and solve it exactly. 15 marks