1. Give a pseudo-code description of the O(n)-time algorithm for computing the power function p(x,n). Also, draw the recursion trace of this algorithm for the computation of p(2,5).

2. Give a C++ description of Algorithm Power for computing the power function p(x,n) (Code Fragment 4.4).

Code Fragment 4.4: Computing the power function using linear recursion. As a more interesting example of algorithm analysis, let us consider the problem of raising a number x to an arbitrary nonnegative integer, n. That is, we wish to compute the power function p(x,n), defined as p(x,n) = xn. This function has an immediate recursive definition based on linear recursion:

This definition leads immediately to a recursive algorithm that uses O(n) function calls to compute p(x,n). We can compute the power function much faster than this, however, by using the following alternative definition, also based on linear recursion, which employs a squaring technique:

To illustrate how this definition works, consider the following examples:

2⁴ = 2^(4/2)= (2^4/2)² = (2²)² = 4² = 16

2⁵ = 2¹+^(4/2)2 = 2(2^4/2)² = 2(2²)² = 2(4²) = 32

2⁶ = 2^(6/2)2 = (2^6/2)² = (2³)² = 8² = 64

2⁷ = 2¹+^(6/2)2 = 2(2^6/2)² = 2(2³)² = 2(8²) = 128

This definition suggests the algorithm of Code Fragment 4.4.

Algorithm Power(x,n):

Input: A number x and integer n ≥ 0

Output: The value xn

ifn= 0 then

return1

ifnis odd then

y← Power(x, (n−1)/2)

returnx·y ·y

else

y← Power(x,n/2)

returny·y

3. Draw the recursion trace of the Power algorithm (Code Fragment 4.4, which computes the power function p(x,n)) for computing p(2,9).

4. There is a well-known city (which will go nameless here) whose inhabitants have the reputation of enjoying a meal only if that meal is the best they have ever experienced in their life. Otherwise, they hate it. Assuming meal quality is distributed uniformly across a person’s life, what is the expected number of times inhabitants of this city are happy with their meals?