Algorithm Analysis

Problem: We want to write an algorithm that ...

precondition: given a non-empty and non-increasing array A[1..n], and a number x,

postcondition: returns a number q 0..n that partitions A along x, that is:

if i 1..n satisfies i q then A[i] x, and

if i 1..n satisfies i > q then A[i] < x.

For example, if A[1..6] is given by

1 2 3 4 5 6

8

7

5

5

4

2

then

if x = 5 then q = 4 must be returned

if x = 6 or x = 7 then q = 2 must be returned

if x = 8 then q = 1 must be returned

if x = 9 then q = 0 must be returned.

To implement this specification we shall use the binary search principle, and develop an iterative algorithm of the form

Partition(x, A, n)

P

while G

q (lo + hi) div 2

B

return R (in q)

which uses variables lo and hi, and where the loop invariant has 3 parts:

(1) 1 lo hi + 1 n + 1

(2) A[i] x for all i 1..n with i < lo

(3) A[i] < x for all i 1..n with hi < i.

We shall now develop the preamble P, the loop guard G, (the remaining) loop body B, and the return expression R

1. Preamble We shall find a suitable P.

1. Tell why lo 2; hi n will in general not establish .

2. Write a sequence of assignments that will always establish (you dont need to argue why).

2. Loop guard and return expression

1. Argue that lo < hi is not a good loop guard.

2. Instead, we shall choose lo hi as the loop guard G.

(a) At loop exit, what is the relationship between lo and hi? (be as precise as possible).

(b) Find a return expression R that establishes the postcondition (no need to argue why).

3. Loop body

1. First consider the case where B is given by

if A[q] x

lo q

else

hi q

(a) Argue that this choice will maintain part (2) of . (You are not asked to show that (1) and (3) are maintained, but (3) can be argued for in a similar way, and (1) is easy to see.)

(b) Argue that with this choice, the loop may not terminate.

2. Write B such that is maintained and termination is ensured (you do not need to argue for these properties).