3. Let P(n) be the proposition that: for all k, with 1 k n, (C)=(-1)+(**) (a)...

 

Transcribed Image Text:

3. Let P(n) be the proposition that: for all k, with 1 k n, (C)=(-1)+(**) (a) Prove that P(n) holds for all n 1. (Note: it is possible to do this without using induction) (10 marks) We can compute (") from the formula given in lectures, however this can often require computing unnecessarily large numbers. For example, (15) 253338471349988640 which can be expressed as a 64-bit integer, but 100! is larger than a 512-bit integer. We can, however, make use of the equation above to compute (") more efficiently. Here are two algorithms for doing this: chooseRec(n,k): if k=0 or k=n: return 1 else: chooseRec(n-1,k-1) y: chooseRec(n-1,k) return z+y chooselter(n,k): Let C be a nxn array for m=1 ton: C[m][0]=C[m][m]=1 for j 1 to m-1: Cm Cm-1][1] +C[m-11 return C[n][k] Let free(n,k) be the running time for chooseRec(n, k), and let ter(n) be the running time for chooselter(n, k). Let Tree(n) maxosks free(n,k) and Tier(n) maxosks fiter (n. k) (so Tec(n) free(n, k) for all k, and likewise for Ther(n)). (b) Give an asymptotic upper bound for Tec(n). Justify your answer. (c) Give an asymptotic upper bound for Tier (n). Justify your answer. (10 marks) 3. Let P(n) be the proposition that: for all k, with 1 k n, (C)=(-1)+(**) (a) Prove that P(n) holds for all n 1. (Note: it is possible to do this without using induction) (10 marks) We can compute (") from the formula given in lectures, however this can often require computing unnecessarily large numbers. For example, (15) 253338471349988640 which can be expressed as a 64-bit integer, but 100! is larger than a 512-bit integer. We can, however, make use of the equation above to compute (") more efficiently. Here are two algorithms for doing this: chooseRec(n,k): if k=0 or k=n: return 1 else: chooseRec(n-1,k-1) y: chooseRec(n-1,k) return z+y chooselter(n,k): Let C be a nxn array for m=1 ton: C[m][0]=C[m][m]=1 for j 1 to m-1: Cm Cm-1][1] +C[m-11 return C[n][k] Let free(n,k) be the running time for chooseRec(n, k), and let ter(n) be the running time for chooselter(n, k). Let Tree(n) maxosks free(n,k) and Tier(n) maxosks fiter (n. k) (so Tec(n) free(n, k) for all k, and likewise for Ther(n)). (b) Give an asymptotic upper bound for Tec(n). Justify your answer. (c) Give an asymptotic upper bound for Tier (n). Justify your answer. (10 marks)