Chapter 1 Homework Use the statistics algorithm from the text to compute the

Algorithms 1

Solutions

Chapter 1 Getting Started

1.1 Algorithms

1. Use the statistics algorithm from the text to compute the mean, ¯x, and the

standard deviation, s, of the data set: −5,−3,2,−2,1.

The inputs are

2. With n= 4, use the trapezoidal rule algorithm from the text to approximate

the value of the definite integral

Z1

0

1

1 + x2dx.

2Section 1.1

3. Use the square root algorithm from the text to approximate √5. Take x0= 5,

ǫ= 5 ×10−4and Nmax = 10.

Let a= 5,x0= 5,ǫ= 5×10−4, and Nmax = 10. The first iteration of the square

root algorithm yields

In the second iteration, we find

In the third iteration, we find

The fourth iteration yields

Algorithms 3

4. A diﬀerent scheme for approximating the square root of a positive real number

ais based on the recursive formula

xn+1 =x3

n+ 3xna

3x2

n+a.

(a) Construct an algorithm for approximating the square root of a given posi-

tive real number ausing this formula.

(b) Test your algorithm using a= 2 and x0= 2. Allow a maximum of 10

iterations and use a convergence tolerance of ǫ= 5 ×10−5. Compare the

performance of this algorithm with the one presented in the text.

(a) GIVEN: nonnegative real number a

(b) Let a= 2,x0= 2,ǫ= 5 ×10−5, and Nmax = 10. The first iteration of the

algorithm from part (a) yields

4Section 1.1

5. Let Abe an n×mmatrix and Bbe an m×pmatrix. The n×pmatrix C=AB

has elements defined by

cik =

m

X

j=1

aij bjk

for each i= 1,2,3,…,n and each k= 1,2,3,…,p. Construct an algorithm to

compute the product of two matrices.

6. Consider the computation of the following sum,

n

X

i=1

n

X

j=1

aibj,

where the aiand bjare real numbers.

(a) How many multiplications and how many additions are required to com-

pute the sum? Each answer should be a function of n.

(b) Modify the summation to an equivalent form which reduces the number

of operations needed. How many multiplications and how many additions

are required to compute the sum in its revised form?

Algorithms 5

(a) As written, forming the product of aiand bjfor each possible combination

7. Let abe a non-zero real number. For any x0satisfying 0 < x0<2/a, the

recursive sequence defined by

xn+1 =xn(2 −axn)

converges to 1/a.

(a) Construct an algorithm for approximating the reciprocal of a given non-

zero real number ausing this formula.

(b) Test your algorithm using a= 37 and x0= 0.01. Allow a maximum of 10

iterations and use a convergence tolerance of ǫ= 5 ×10−4.

(a) GIVEN: non-zero real number a

(b) Let a= 37,x0= 0.01,ǫ= 5 ×10−4, and Nmax = 10. The first iteration of

the algorithm from part (a) yields

6Section 1.1

The third iteration then yields

STEP 1: iter = 3

STEP 4: x0= 0.026356335

In the fourth iteration, we calculate

8. Given two positive integers aand b, the greatest common divisor of aand b

is the largest integer which divides both aand b;i.e., the largest integer nfor

which both a/n and b/n are integers.

(a) Construct an algorithm to compute the greatest common divisor of two

positive integers.

(b) How many divisions does your algorithm require?

(a) GIVEN: positive integers aand b

9. The inner product, or dot product, of two n-vectors xand yis given by

x·y=x1y1+x2y2+x3y3+···+xnyn.

(a) Construct an algorithm to compute the inner product of two n-vectors.

(b) Apply your algorithm to calculate the inner product of the vectors

x=−3 4 1 2 Tand y=1−3 2 5 T

Algorithms 7

(a) GIVEN: n-vectors xand y

(b) The inputs are the vectors

10. The linear correlation coefficient for nordered pairs (xi, yi) is given by the

formula

r=nPn

i=1 xiyi−(Pn

i=1 xi) (Pn

i=1 yi)

qnPn

i=1 x2

i−(Pn

i=1 xi)2qnPn

i=1 y2

i−(Pn

i=1 yi)2.

(a) Construct an algorithm to compute the linear correlation coefficient for a

given set of ordered pairs.

(b) Apply your algorithm to compute the linear correlation coefficient for the

following set of ordered pairs:

xi3 7 9 2 7 0 3

yi-5 10 15 -8 11 -10 -4

(a) GIVEN: ordered pairs (xi, yi)

(b) Working sequentially through the steps of the algorithm, we find

STEP 1: xsum =ysum =x2sum =y2sum =xysum = 0

STEP 2: i= 1:xsum = 0 + 3 = 3; ysum = 0 + (−5) = −5

11. The midpoint rule approximates the value of a definite integral using the formula

Zb

a

f(x)dx ≈2h

n

X

j=1

f(xj),

where h= (b−a)/2nand xj=a+ (2j−1)h.

(a) Construct an algorithm to approximate the value of a definite integral using

the midpoint rule.

Algorithms 9

(b) Apply your algorithm to approximate the value of R2

1dx/x. Take n= 4.

Compare the approximation obtained from the midpoint rule with the

approximation obtained from the trapezoidal rule.

(a) GIVEN: the limits of integration aand b

(b) Matching this specific problem to the general pattern Rb

12. Consider the following algorithm for the trapezoidal rule:

GIVEN: the limits of integration aand b

the integrand f

the number of subintervals n

STEP 1: compute h= (b−a)/n; and initialize sum to 0

STEP 2: for ifrom 1 to n−1

add 2f(a+ih) to sum

STEP 3: add f(a) and f(b) to sum

OUTPUT: (h/2)sum

Compare the number of arithmetic operations required by this algorithm to the

number of operations required by the algorithm presented in the text.

Aside from the operations needed to evaluate f, the trapezoidal rule algorithm

presented in the text uses 2n+ 1 additions/subtractions (one in STEP 1, 2(n−1)

10 Section 1.1

13. Rewrite the algorithm for the trapezoidal rule which was presented in the text to

reduce both the number of additions and the number of multiplications/divisions

by one.

The key is to observe that

This suggests modifying the trapezoidal rule algorithm to

14. Let P(x) = anxn+an−1xn−1+···+a1x+a0be an n-th degree polynomial

with all real coefficients, and let x0be a given real number.

(a) Treating integer powers as repeated multiplication, how many multiplica-

tions and how many additions are required to evaluate P(x) at x=x0?

(b) Devise an algorithm for computing the value of an n-th degree polynomial

which reduces the required number of arithmetic operations? How many

multiplications and how many additions are required by your algorithm?

Algorithms 11

(b) To devise a more efficient scheme for evaluating an nth-degree polynomial, we

rewrite the polynomial in nested form:

For Exercises 15 – 18, make use of the fact that when the sum of a convergent

alternating series is approximated using the sum of the first nterms, the error

in this approximation is smaller than the magnitude of the (n+1)-st term; i.e.,

if P(−1)nanis an alternating series with sum S, then



S−

n−1

X

k=0

(−1)kak

< an.

15. The value of πis given by

π= 4

∞

X

n=0

(−1)n

2n+ 1 = 4 1−1

3+1

5−1

7+−···.

12 Section 1.1

(a) GIVEN: convergence parameter ǫ

16. The value of 1/e is given by

1/e =

∞

X

n=0

(−1)n

n!= 1 −1

1! +1

2! −1

3! +−···.

(a) Construct an algorithm to approximate the value of 1/e to within a speci-

fied tolerance, ǫ.

(b) Test your algorithm with a tolerance value of ǫ= 5 ×10−7.

(a) GIVEN: convergence parameter ǫ

17. The value of sin(π/10) is given by

sin π

10=

∞

X

n=0

(−1)n

(2n+ 1)! π

102n+1

=π

10−1

3! π

103

+1

5! π

105

−1

7! π

107

+−···.

(a) Construct an algorithm to approximate the value of sin(π/10) to within a

specified tolerance, ǫ.

Algorithms 13

(b) Test your algorithm with a tolerance value of ǫ= 5 ×10−7. Note that the

exact value of sin(π/10) is 1

4(√5−1).

(a) GIVEN: convergence parameter ǫ

18. The value of cos(π/5) is given by

cos π

5=

∞

X

n=0

(−1)n

(2n)! π

52n

= 1 −1

2! π

52

+1

4! π

54

−1

6! π

56

+−···.

(a) Construct an algorithm to approximate the value of cos(π/5) to within a

specified tolerance, ǫ.

(b) Test your algorithm with a tolerance value of ǫ= 5 ×10−7. Note that the

exact value of cos(π/5) is 1

4(√5 + 1).

(a) GIVEN: convergence parameter ǫ