Need help for wrinting Algorithms/ Pseudocode

1. The binary method of exponentiation computes a^n for any positive integer n using the fact that a^n =(a^(n/2))^2 if n is even,and a^n =a·a^n−1 If n is odd. Please see the picture attached for this question. (a) Give the pseudocode for a recursive algorithm computing a^n 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. (b)Find out the exact total number of multiplications performed when using your algorithm to compute a^n 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. [login to view URL] the following problem in computational geometry: Input: an array Q[1..n] of pairs of integers (x, y) representing the x- and y-coordinates of the vertices of a convex polygon P in the plane, given in an arbitrary order. Output: an array C[1..n] of pairs of integers such that C[1], C[2], . . . , C[n] gives the consecutive vertices of P in clockwise order, starting from some initial vertex. Give an algorithm that uses O(nlgn) time. In your algorithm, you are not allowed to call Graham’s scan directly as a subroutine. Instead, borrow ideas from Graham’s scan and write an algorithm that is simpler than it. Include sufficient details in your pseudocode, such as the computational steps that locate the first point in C.