Explain an algorithm that computes 2^n using Θ(log n) multiplications. Justify why your algorithm uses Θ(log n) multiplications. a. Consider the case where n is a power of 2, i. e., n = 2^k . Use Θ(k) multiplications to obtain 2n . Hint: Note that 2^(2^k) = (2^(2^k−1) )^2 .
b. Consider the case where n = 2^k + 2^(k−1) . Use Θ(k) multiplications to obtain 2^n . Hint: Note that 2^(2^k+2^(k−1)) = 2^(2^k) × 2^(2^(k−1)) .
c. Generalize the ideas in parts (a) and (b) to compute 2n using Θ(log n) multiplications for any positive integer n.

3. ranga ramasesh is the operations manager for a firm that is trying to decide which one of four countries it should research for possible outsourcing providers. the first step is to select a country based on cultural risk factors, which are critical to eventual business success with the provider. ranga has reviewed outsourcing provider directories and found that the four countries in the table that follows have an ample number of providers from which they can choose. to aid in the country selection step, he has enlisted the aid of a cultural expert, john wang, who has provided ratings of the various criteria in the table. the resulting ratings are on a 1 to 10 scale, where 1 is a low risk and 10 is a high risk. john has also determined six criteria weightins: trust, with a weight of 0.3; quality, with 0.2; religious, with 0.1; individualism, with 0.2; time, with 0.1; and uncertainity, with 0.1. using the factor-rating method, which country should ranga select? why? (2 points)