SUNY Geneseo Department of Computer Science

Introduction to Induction

Return to List of Lectures

Questions?

Induction

Main technique for proofs about recursion, e.g., divide-and-conquer

kth smallest element in an unsorted array A[1..n]

• Example
  • A = [2, 6, 13, -1, 4, 1]
  • k = 2
  • Result should be 1
  • If k = 5 algorithm should return 6, which it would do in part by partitioning array into [-1, 1, 2, 6, 13, 4] and then looking in the [6, 13, 4] section without ever caring which of the earlier elements was the smallest, second smallest, etc.
• Precondition: 0 < k ≤ ( last - first + 1 )

        kthSmallest( A, first, last, k )
            if last < first
                // array section is empty, error!
            else
                p = partition( A, first, last )     // as in Quicksort
                if k < p-first+1
                    kthSmallest( A, first, p-1, k )
                else if k > p-first+1
                    kthSmallest( A, p+1, last, k+p )
                else
                    return A[p]

• Prove that this works (or discover that it doesn’t and fix)
• Proof by induction on section size, last - first + 1
  • Base case: section contains 1 element (the smallest section that can have a k satisfying the precondition)
    • k must be 1 according to the precondition, and the algorithm should return the only element in the section, A[first]
    • In this case last = first, so partition returns first, i.e., p = first
    • k = 1 is neither less than nor greater than p - first + 1 = first - first + 1 = 1
    • (Note that we found a bug in our original algorithm at this point in the proof, since the original algorithm compared k to p, and we couldn’t show that k = p)
    • Algorithm therefore executes the return A[p] which returns the desired A[first] since p = first
  • Induction hypothesis: the algorithm is correct whenever last - first + 1 ≤ a for some a ≥ 1
    • This is strong induction, generally useful with divide-and-conquer algorithms because you don’t know how much smaller the sub-problems are than the original
    • Prove that the algorithm is correct when last - first + 1 = a+1
    • partition returns a p such that first ≤ p ≤ last
    • Three cases: k < p-first+1, k > p-first+1, or k = p-first+1
      • If k < p-first+1 then partition has put the kth smallest element somewhere in the left section of the array, i.e., between positions first and p-1. The recursive call searches this section, to which the induction hypothesis applies because its size is (p-1) - first + 1 = p - first ≤ last - first = a. The algorithm thus returns the correct result in this case.
      • if k > p-first+1, the kth smallest element is somewhere in the right section, i.e., between positions p+1 and last. This section is of size last - (p+1) + 1 = last - p ≤ last - first = a, so the induction hypothesis again applies. But why are we looking for the (k+p)th smallest element in this section? This is bug number 2 in the algorithm!
• Moral: conscientious attempts to prove a new algorithm correct are valuable ways to find bugs in its design, bugs which almost always exist in the first version of any algorithm
• We’ll fix this last bug next time and finish this proof, then go look at some more examples

Hand out induction problem set

• But change the due date to Friday, February 15

Next

More induction

No reading!