SUNY Geneseo Department of Computer Science

Designing Binary Search

Previous Lecture

Misc

Hand out Lab 7

First hour exam next Tuesday, March 2

• Covers material since start of course (Object oriented abstraction, Proof, Experiments, Conditionals, Recursion, Induction, Recurrences)
• Whole class period
• 4 - 5 short-answer questions
• Open book, open notes, open computer
• Closed person
• Sample Exam on the Web
• Elegance is good

Questions?

Lab data analysis?

• Given list of times in mS
• How to relate average of worst case to closed form from recurrence
• e.g., average worst case time = 760 mS
  • Closed form f(n) = 2ⁿ-1
• Key idea is growth with n
• Averages for multiple values of n
• Compare to 2ⁿ-1 for the same n's

Practice test, question 3

• How to change code for timing
• Put calls to System.currentTimeMillis around r.paintAndMove()

Induction and upcoming test?

• Proofs could be anything from pure prose (e.g., proof about non-mathematical algorithm), maybe with pictures, to pure math (e.g., closed forms)
• Clear rigorous logic is vital

Mini-Assignment

    int sumEvens( int n ) {
        if ( n == 2 ) {
            return 2;
        }
        else {
            return n + sumEvens( n - 2 );
        }
    }

Recurrence

• f(n) = 1 if n = 2
• f(n) = 3 + f(n-2) if n > 2

Prove that f(n) = (3n-4)/2 is a closed form for this

• Induction on n
• Base case, n = 2
  • (3n-4)/2 = (3*2 - 4 ) /2 = (6-4)/2 = 1
  • = f(n) from recurrence
• Induction hypothesis
  • Assume f(k-2) = (3(k-2)-4)/2
• Show f(k) = (3k-4)/2
  • f(k) = 3 + f(k-2) from recurrence
  • = 3 + (3(k-2)-4)/2 by induction hypothesis
  • = 3 + (3k-6-4)/2
  • = 3 + (3k-10)/2
  • = 6/2 + (3k-10)/2
  • = (6 + 3k-10)/2
  • = (3k-4)/2

Binary Search

End-to-end design, correctness, and performance analysis example.

Search a section of a sorted array between positions low and high for a value x. Return true if x is there, false if not.

Look at element n/2, see if < x, > x, or = x

• Return true if =
• Search top half if < x
• Search bottom half if > x

    boolean search( A, x, low, high )
        if ( low <= high )
            mid = (low + high) / 2
            if ( A[mid] < x )
                return search( A, x, mid+1, high )
            else if ( A[mid] > x )
                return search( A, x, low, mid-1 )
            else
                return true
        else
            return false

Try to prove that this works

• Induction on number of elements between positions low and high, i.e., n = high - low + 1
• Base case, n = 1
  • Oops, problem with test for a trivial failing search (original "if ( low < high )" corrected above)
• Try again... oops, recursions don't solve smaller problems
  • Note: The fact that we are considering recursive messages in the proof's "base case" at all indicates that there's really a simpler base case for the proof that would correspond more closely to the algorithm's base case.
  • (Original "mid" in recursive messages corrected to "mid+1" and "mid-1" above)

Next

• Finish the analysis of Binary Search
• This will be after break, as we have the test Tuesday and I am out of town Thursday. I'm trying to arrange tours/talks on the "behind-the-scenes" computing infrastructure at Geneseo for Thursday.

Next Lecture