Problem Set 5—Inductive Proofs of Correctness

Purpose

Background

Exercise

The following divide and conquer algorithms may or may not be correct. For each algorithm, state precisely what it should mean for that algorithm to be “correct” and attempt to prove the algorithm’s correctness by induction. Each proof should either show that the algorithm is correct, or, by the way the proof fails, pinpoint a bug in the algorithm.

Algorithm 1

Imagine an array that begins with a long sequence of zeros, after which everything in the array is non-zero. You want to find the place in the array where the non-zero data begins. The following algorithm supposedly does this, given the precondition that there is at least one non-zero element in A between positions first and last inclusive:

    firstNonZero( A, first, last )
        if first == last
            return first
        else
            mid = ⌊( first + last ) / 2⌋
            if A[mid] == 0
                return firstNonZero( A, mid+1, last )
            else
                return firstNonZero( A, first, mid )

Algorithm 2

The following algorithm is a variation on binary search. It works on an array that is sorted into increasing order, and that may contain duplicate entries. Given a value, k, that might be in the array, the algorithm supposedly returns the number of times that k appears. The first and last parameters are inclusive lower and upper bounds on the section of A in which to count occurrences of k.

    count( k, A, first, last )
        if first > last
            return 0
        else
            mid = ⌊( first + last ) / 2⌋
            if k < A[mid]
                return count( k, A, first, mid-1 )
            else if k > A[mid]
                return count( k, A, mid+1, last )
            else
                return count( k, A, first, mid-1 ) + count( k, A, mid+1, last )

Algorithm 3

Here is merge sort, much as presented in our textbook (see section 2.3.1). The book proves that the merge procedure is correct, i.e., that given an array A and indices into it first, mid, and last such that the elements of A between positions first and mid (inclusive) are sorted into increasing order, and the elements between positions mid+1 and last (also inclusive) are sorted, merge leaves all elements of A between positions first and last (inclusive) sorted. I have therefore left out the pseudocode for merge; assume that it is exactly as shown in the text and therefore that it is correct. The text does not, however, prove that the overall sorting algorithm is correct. Using the assumption that merge is correct, prove that my merge sort as a whole is correct (or find a flaw in the algorithm by trying to prove it correct).

    mergesort( A, first, last )
		if first < last
			mid = ⌊( first + last ) / 2⌋
			mergesort( A, first, mid-1 )
			mergesort( A, mid, last )
			merge( A, first, mid-1, last )

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Please bring a written solution to your meeting. During the meeting, I will look over your solution, give you my reactions to it, answer any questions you have about it, etc.

Meetings should take about 15 minutes, although you are welcome to reserve a longer time if you have a lot of questions. Please sign up for your meeting on the schedule outside my office or via Google calendar. If you work in a group, the entire group can schedule a single meeting with me. You should be ready to grade this exercise shortly after class on the “Complete By” date above; however, you have until the end of the “Grade By” date to actually meet with me.