PPT Slide
Iteration of a loop: One execution of loop body S (when C is true).
Loop invariant: An assertion (true-false statement) that is maintained by each iteration --if the invariant is true before an iteration, it is true after iteration.
3. Look through the lecture notes for the development of other loops from loop invariants. Practice developing these, too.
4. Exercises. Answers are after the exercises.
(a) Write an algorithm to store the sum of the elements of b[h..k-1] in x. Use the loop invariant P:
x is the sum of b[h..j-1], i.e.
(b) Write an algorithm to store the sum of the elements of b[h..k] in x. Use the loop invariant P:
x is the sum of b[h..j-1], i.e.
(c) Write an algorithm to store the sum of the elements of b[h..k-1] in x. Use the loop invariant P:
x is the sum of b[j..k-1], i.e.
(d) Write an algorithm to store the sum of the elements of b[h..k-1] in x. Use the loop invariant P:
x is the sum of b[j+1..k-1], i.e.
(e) Write an algorithm that, given n >= 1, stores in j the smallest power of 2 that is greater than n. (Note: the pow-ers of 2 are 1, 2, 4, 8, 16, … ). Use the loop invariant P:
the powers of 2 that are less than j are at most n
(f) Write an algorithm that, given n >= 0, stores in j the smallest square that is greater than n. (Note: the squares are 0, 1, 4, 9, 16, 25, … ). Use the loop invariant P:
P: 1 <= j and (j-1)*(j-1) <= n
(g) It is known that x is in b[h..k]. Write an algorithm to store in j the index of the last occurrence of x in b[h..k]. Use the loop invariant:
P: h <= j <= k and x is not in b[j+1..k], i.e.
(h) Write an algorithm that, given a<b, stores the maxi-mum value of m[a..b-1] in x. Use the loop invariant P:
P: x is the maximum of m[a..k-1]
An empty segment has no maximum, so it makes sense to initialize so that m[a..k-1] has one value in it.