Design and Analysis of Algorithms

Additional Exercises with Solutions 725

else x = x – 1, z = z + y;

end

end

Prove that

{m is a non-negative integer and n is an integer} S {z = mn}

15. (Maximum of an array) Let S denote the program

k = 1, m = a[1];

while k < n

do k = k + 1;

if a[k] > m then m = a[ ] end

end

Prove that {n is a positive integer} S {m is the largest of all a[1], a[2], . . . a[n]}

E.1.3 Chapter 7: Design by Proof Rules

1. (Table of cubes) Suppose that we want to build a table of squares where T [k] contains k

2

. A

straightforward approach is to compute k

*

k for each k and store the values in the table. However,

multiplicative operations ...