2. [10 marks] The binary method of exponentiation computes a for any positive integer n using...

 

Transcribed Image Text:

2. [10 marks] The binary method of exponentiation computes a" for any positive integer n using the fact that an = (a/2)2 if n is even, and an = a an-1 if n is odd. (a) [5 marks] Give the pseudocode for a recursive algorithm computing an where n is a positive integer, using the above idea. Do NOT use memoization. In your solution, when n is even, there should be only one (explicit) recursive call among your pseudocode for this case. For this sub-question, no explanation, justification, or analysis is required; simply give your pseudocode. (b) [5 marks] Find out the exact total number of multiplications performed when using your algorithm to compute an for any positive integer n. Use the substitution method, i.e., make a guess and then prove its correctness by induction. Hint: It may be helpful to consider the number of 1-digits in the base-2 expression of n. Let s2(n) be this value. You can use s2(n) as one of the additive terms in your solution. 2. [10 marks] The binary method of exponentiation computes a" for any positive integer n using the fact that an = (a/2)2 if n is even, and an = a an-1 if n is odd. (a) [5 marks] Give the pseudocode for a recursive algorithm computing an where n is a positive integer, using the above idea. Do NOT use memoization. In your solution, when n is even, there should be only one (explicit) recursive call among your pseudocode for this case. For this sub-question, no explanation, justification, or analysis is required; simply give your pseudocode. (b) [5 marks] Find out the exact total number of multiplications performed when using your algorithm to compute an for any positive integer n. Use the substitution method, i.e., make a guess and then prove its correctness by induction. Hint: It may be helpful to consider the number of 1-digits in the base-2 expression of n. Let s2(n) be this value. You can use s2(n) as one of the additive terms in your solution.