Computer Algorithms II Lecture Notes

9 October 2007 • Algorithm Correctness

Outline

• Specification

• Correctness

• Correctness conditions.

Binary Search

• Given an ascending ordered array a and a value x, return

  • i such that a[i] = x or

  • -1 if no such i exists.

• Each search should take no more than O(log n) comparisons.

Algorithm Correctness

• An algorithm is correct if it does what it's supposed to do.

• Even this definition is slippery:

  • What is the algorithm supposed to do?

  • Under what conditions?

  • How do you check if the algorithm did what it was supposed to do?

Algorithm Specification

• An algorithm's specification describes what it's supposed to do.

  • Defining good specifications is hard.

  • As is figuring out what “good” means.

• As a rule of thumb, a good specification

  • describes everything you need to know,

  • describes nothing you don't need to know.

• Of course, these depend on points of view.

Binary Search Example

• The binary search specification describes

  a as array in an ascending order.

  The return value i if a[i] = x

  The return value -1 if no such i exists.

  The O(log n) limit on comparisons.

• Anything missing? Anything not needed?

  • Finding good specifications is iterative.

Correctness

• Should an algorithm be correct all the time?

• What happens if being correct all the time is impossible? Or expensive?

  • How is it impossible to be correct all the time?

• The specification should be made clear under what circumstances correctness is expected.

  • It might also want to indicate what happens when expectations are not met.

Binary Search Example

• Under what conditions does the binary-search algorithm work correctly?

  • a must be in ascending order.

• What happens if a isn't in ascending order?

  • The specification could cover non-ascending order arrays.

  • An implicit fall-back to “undefined behavior”.

Correctness Conditions

• A specification is a contract between the caller and the called.

• A contract lays out obligations for both parties involved.

  • The caller's obligations involve the inputs specified.

  • The called's obligations involve the output specified.

• Failure to meet obligations is a breach of contract.

Key Idea

• A value in the array must be within a range of indices.

  • If the value's in the array; it doesn't have to be.

• Abbreviate the key idea with in-range(). in-range(l, r) means

  If v is in a, it must be in a[l..r].

Idea Check

• Does this key idea help solve the problem?

  • If l = r, then either a[l] equals v or it doesn't.

  • If l > r, then v isn't in the array.

  • If l < r, then more work is needed.

• This check gives some programming hints.

Program Sketch

l, r = 1, n
while true
  // in-range(l, r)
  if l = r
    return a[l] = v ? l : -1
  if l > r
    return -1
  if l < r
    // do more work

Reducing the Range.

• If the range is larger than 1, it needs to be made smaller.

• The smallest it can be reduced is by one:

  l + 1 to r or l to r - 1.

• The most useful reduction is by half:

  m = (l + r)/2.

  • Using integer division, which rounds towards zero (truncates).

Reducing the Range..

• How can m = (l + r)/2 help reduce the range?

• Given m, examine a[m]. There are three cases:

  1: a[m] > v
  2: a[m] = v
  3: a[m] < v

• If case 2 (a[m] = v) holds, the search succeeded.

• What about the other cases?

Reducing the Range...

• How can a[m] ≠ v help reduce the range?

• Given that a is sorted, v can't appear in one of the subranges 0..m or m..n, but which one?

• Given that a is sorted in ascending order,

  • a[m] < v means in-range(l, m) doesn't hold,

  • a[m] > v means in-range(m, r) doesn't hold.

Reducing the Range....

• If in-range(l, r) holds and in-range(l, m) doesn't hold, then in-range(m + 1, r) holds.

  

• Similarly in-range(l, r)and not in-range(m, r) means in-range(l,m - 1).

Binary Search

int find(a[], n, v)

  l, r = 0, n - 1
  while true
    // in-range(l, r)
    if l > r
      return -1
    else
      m = (l + r)/2
      if a[m] = v, return m
      if a[m] < v, l = m + 1
      if a[m] > v, r = m - 1

Invariants

• in-range() is an example of an invariant.

• An invariant is a statement that's always true during execution.

• Maintaining the invariant while executing keeps the program on track.

• At execution's end, the invariant and changed program state should combine to produce the correct results.

• Every procedure should have an invariant.

Iterations

• Correct code eventually produces a correct result.

• Non-terminating code can't produce a correct result.

• Straight-line code doesn't have a termination problem.

• Termination for code with loops is less clear.

  • Correctness for looping code includes an argument for termination.

Termination Arguments

• A termination argument is based on reducing a non-negative value.

• Each iteration should reduce the value.

  • Non-negative values can only reduce to zero.

  • At zero, the iterations stop.

• The value is usually tied to the loop's data structure.

  • Array elements, or tree nodes for example.

Binary Search Example

• For binary search, the size of the region r - l can be the value.

  • The number of unsearched elements in the array.

• When the region's empty (= 0), the search ends (in failure).

• Each iteration should reduce the region by at least one.

Binary Search Analysis

while true
  if l > r
    return -1
  else
    m = (l + r)/2
    if a[m] = v, return m
    if a[m] < v, r = m - 1
    if a[m] > v, l = m + 1

• The crucial observation is l ≤ m < r.

  • l = m may not reduce the range.

  • l = m + 1 reduces the range.

Example 1

find(start, end, x, size)
  m = size/2
  if a[m] < x
    return find(start, m - 1, x, m)
  if a[m] > x
    return find(midpoint + 1, end, x, m)
  if a[m] = x
    return m
  if size = 1
    return -1

Analysis

find(start, end, x, size)
  m = size/2
    // What's the interval?
  if a[m] < x
    return find(start, m - 1, x, m)
      // The correct half-interval?
  if a[m] > x
    return find(m + 1, end, x, m)
      // The correct half-interval?
  if a[m] = x
    return m
  // How do you get here?
  if size = 1
    return -1

Example 2

find(a, x)
  first = 0
  last = a.size()
  i = last/2
  while (a[i] ≠ x) or 
        (last ≠ i and first ≠ i)
    if a[i] > x
      last = i
    else if a[i] < x
      first = i
    i = first + (last - first)/2
  if a[i] = x
    return x
  return -1

Analysis

while (a[i] ≠ x) or 
      (last ≠ i and first ≠ i)
  // Is a[i] defined?
  if a[i] > x
    last = i
  else if a[i] < x
    first = i
  i = first + (last - first)/2
  // Is the interval smaller?
if a[i] = x
  return x
return -1

Example 3

find(a, first, last, key)
  m = (first + last)/2
  if m > last
    return -1
  if a[m] = key
    return m
  if a[m] > key
    return find(a, m + 1, last, key)
  return find(a, first, m - 1, key)

Analysis

find(a, first, last, key)
  m = (first + last)/2
  if m > last
    return -1
  if a[m] = key
    return m
  if a[m] > key
    return find(a, m + 1, last, key)
      // The correct half interval?
  return find(a, first, m - 1, key)
    // The correct half interval?

Summary

• Figure out what the code's supposed to do.

  • Get the specification.

• Determine an invariant that always holds and meets the code's specification at the end.

  • Also determine if there will be an end if needed.

• Structure the code to maintain the invariant.