Homework Week 9

Problem 24

Devise a recursive algorithm to find \(a^{2^n}\), where \(a\) is a real number and \(n\) is a positive integer. Hint: Use \(a^{2^{n+1}}=(a^{2^n})^2\).

Problem 25

How does the number of multiplications used by the algorithm in Exercise 24 compare to the number of multiplications used by Algorithm 2 to evaluate \(a^{2^n}\)?

Problem 32

Devise a recursive algorithm to find the \(n\)th term of the sequence defined by:

\[ a_0=1, \quad a_1=2, \quad a_2=3, \quad a_n=a_{n-1}+a_{n-2}+a_{n-3}\text{ for }n\ge3. \]

Problem 33

Devise an iterative algorithm to find the \(n\)th term of the sequence defined in Exercise 32.

Problem 34

Compare recursive and iterative efficiency for the sequence in Exercises 32 and 33.

Problem 45

Use merge sort to sort:

\[ b,d,a,f,g,h,z,p,o,k. \]

Problem 1

Verify correctness of the program segment:

y := 1
z := x + y

with initial assertion \(x=0\) and final assertion \(z=1\).

Problem 2

Verify correctness of the program segment:

if x < 0 then x := 0

with initial assertion \(T\) and final assertion \(x\ge 0\).

Problem 3

Verify correctness of the program segment:

x := 2
z := x + y
if y > 0 then z := z + 1
else z := 0

with initial assertion \(y=3\) and final assertion \(z=6\).

Problem 4

Verify correctness of a program that assigns the minimum of \(x\) and \(y\):

if x < y then min := x
else min := y

Final assertion:

\[ (x\le y \land \min=x)\lor(x>y\land \min=y). \]

Problem 7

Prove correctness of the power algorithm using a loop invariant.

Problem 9

Read Example 5, then prove correctness of the multiplication program from Example 5.

Problem 12

Give a recursive algorithm for the greatest common divisor using the Euclidean algorithm.