Question on problems on algorithms, the topics on divide and conquer. Here is th

Question

Question on problems on algorithms, the topics on divide and conquer. Here is the Question

The following is a divide-and-conquer algorithm for finding the maximum value in an array S[1..n]. The main body of the algorithm consists of a call to maximum(1, n). function maximum(x, y) comment return maximum in S[x..y). if y - x lessthanorequalto 1 then return(max(S[x], S[y)) else max 1:=maximum(x, [(x + y)/2]) max2:=maximum([(x + y)/2] + 1.y) return(max(max1.max2)) Prove that the algorithm is correct. You may assume that n is a power of 2.

Explanation / Answer

Below is the proof of correctness of the algorithm :

The strategy to prove the correctness of an algorithm is a combination of knowing standard techniques and
inventing new standard ones when the standard techniques don’t apply. To prove correctness of our decide-and-conquer algorithm, we will use a common technique called a loop invariant.

A loop invariant is a set of conditions that are true when the loop is initialized and is true at termination. Loop invariant arguments are analogous to mathematical induction:
We can always use a base case along with an inductive step to show that the desired proposition is true in all cases. One possible loop invariant for this algorithm would be the following:

At each iteration, the active subarray (say it S') consists of all the elements of S which are in between the min(S') and max(S'), and the current index (call it i') has the property that the i'th-smallest element of S' is the ith-smallest element of S.

In order to prove that this is a loop invariant, three things must be shown:

1. True at initialization. Initially, the active subarray is S and the index is i, so the proposition is perfectly true.

2. Maintain each pass through the loop. If the proposition is true at the beginning of an iteration (say with active subarray S' = S'[1,...,n']   and active index i'), then the (k 1)- and (n' k)-element subarrays clearly also have the contiguity property that we desire. Then, if we calls SELECT(S'',i''), it is easy to see by casework that the i''th-smallest element of S'' equals the i'th-smallest element of S', which by hypothesis equals the ith-smallest element of S.

3. True at termination. Since there is not much on the termination step, the proof of maintenance in each pass though the loop is Qquite enough to  show the maintenance at termination.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.