PPT Slide

(i) Write an algorithm that, given a<=b, stores the maximum value of m[a..b] in x. Use the loop invariant

P: x is the maximum of m[k..b]

(j) Write an algorithm that, given a<=b, stores the index of the maximum value of m[a..b] in h. Use the loop invariant

P: m[h] is the maximum of m[k..b]

(k) (A version of selection sort). Write an algorithm that, given a <= b+1, sorts m[a..b]. Use the invariant P given below. Do not write a loop within the body of the main loop; instead, write commands in the body of the loop as high-level statements, in English.

P:

(l) Write an algorithm that stores into ev the number of even elements in b[0..n] and the number of odd elements into od. Use the invariant P:

P: ev is the number of even values in b[j..n] and

od is the number of odd values in b[j..n]

(m) The rows of two-dimensional integer array b[ ] [ ] is completely allocated. Its rows need not be the same size. Store in h the number of the row with fewest elements. Use the following invariant P:

P: row h has the fewest elements of rows 0..j

(n) Each element b[m] (where 1<=m<=12) of array b[0..12] contains the number of days in month m. (January is month 1, etc.) Given a date (day, month) in two variables day and month, store in n the day of the year on which (day, month) occurs. For example, if January has 30 days, then (5,2), i.e. day 5 of February, occurs on day 35 of the year, and if February has 28 days, then (10,3) occurs on day 68 of the year.

Your algorithm will need a loop plus some other statements. For the loop, use the loop invariant P:

P: 1 <= m <= month and

n is the total number of days in months 1..m-1

P: 1 <= h <= n and

x = F(h) and

y = F(h-1)

(p) Remember that mod(n,m) is the integer r that satisfies

0 <= r < m and n = q* m + r (for some integer q)

From this definition, we can infer:

mod(x,m) = mod(x-m,m) and

if 0 <= x < m, then mod(x,m) = x

Write an algorithm that, given n>=0 and mɭ, stores mod(n,m) in variable r. The algorithm should not use the remainder operator %; instead, it should consist of a single loop (with initialization) that relies on the loop invariant:

P: 0 <= r <= n and

mod(r,m) = mod(n,m)

Hint: you can trutify the invariant with r= n.

Answers to exercises

(a) j= h; x= 0;

// Invariant P (see the problem description)

while (j != k+1) /* or j < k+1 */

{x= x + b[j]; j= j+1;}

(b) j= h; x= 0;

// Invariant P (see the problem description)

while (j != k) /* or j < k */

{x= x+ b[j]; j= j+1;}

// Invariant P (see the problem description)

while (h != j) /* or h < j */

{j= j-1; x= x+b[j]; }

Previous slide Next slide Back to first slide View graphic version