m4_divert(2) m4_define(_commentnesting, 0) m4_define(_begincomment,m4_dnl m4_ifelse(_commentnesting, 0, )) m4_define(_warning,m4_dnl _begincomment()This document was created by gen-_name.html Do not edit this document, edit gen-_name.html._endcomment()) m4_define(_hdrs, ) m4_define(_anchor_no, 0) m4_define(_abs, m4_ifelse(m4_eval($1 < 0), 1, m4_eval(-($1)), $1)) m4_define(hdr, _warning() $2 _warning() m4_ifelse(m4_eval($1 >= 0), 1, m4_define(`_hdrs', _hdrs`'_anchor_no $1 m4_translit(`$2', `,', ) )) m4_define(_anchor_no, m4_eval(_anchor_no + 1)) ) m4_define(usetag, _warning()$2_warning()) m4_define(puttag, _warning()$2_warning()) m4_changecom() m4_define(sps, $1$2) m4_define(sbs, $1$2) m4_define(,_warning()$1_warning()) m4_define(,_warning()$1_warning()) m4_define(itl,_warning()$1_warning()) m4_define(bld,_warning()$1_warning()) m4_define(hrf,_warning()$2_warning()) m4_define(mailat,_warning()hrf(mailto:$1,$1)_warning()) m4_define(nwsgrp, hrf(news:$1, $1)) m4_define(bookref, $1, $2. $3: $4, $5.) m4_define(i2m,m4_ifelse( $1,01,January, $1,02,February, $1,03,March, $1,04,April, $1,05,May, $1,06,June, $1,07,July, $1,08,August, $1,09,September, $1,10,October, $1,11,November,December)) m4_dnl $Revision: 1.5 $, $Date: 1999/12/09 19:16:32 $ CS 512 Test 5 hdr(2, Test 5 - Mathematical Induction and Algorithm Design) hdr(3, CS 512, Algorithm Design)

  1. A complete graph is an undirected graph in which there is an edge between any two vertices in the graph. Derive a recurrence relation for the number of edges in an itl(n)-vertex complete graph. Use induction to prove your recurrence relation is correct.

    Let the value of itl(T)(itl(n)) be the number of edges in an itl(n)-vertex complete graph. Removing one vertex and the itl(n) - 1 adjacent edges leaves a complete graph with itl(n)-1 vertices; that is the number of edges in an itl(n)-vertex complete graph is itl(n) - 1 plus the number of edges in an itl(n)-1-vertex complete graph, or

    itl(T)(itl(n)) = itl(n) - 1 + itl(T)(itl(n) - 1)
    itl(T)(1) = 0
    Unrolling this a few times suggests the recurrence relation equals
    sum(i = 1 to n, i - 1)

    To prove recurrence relation correct, let the hypothesis be

    itl(H)(itl(n)): itl(T)(itl(n)) = sum(itl(i) = 1 to itl(n), itl(i) - 1)
    The base case
    itl(H)(1): itl(T)(1) = 0 = sum(itl(i) = 1 to 1, itl(i) - 1)
    holds. Let itl(H)(itl(j)) be true for itl(j) >= 1 and consider itl(H)(itl(j) + 1). Given a itl(j)-vertex complete graph, I can form a itl(j)+1-vertex complete graph by adding a vertex and itl(j) new edges; that is
    itl(T)(itl(j) + 1) = itl(j) + itl(T)(itl(j))
    Because itl(H)(itl(j)) is true, this gives
    itl(T)(itl(j) + 1) = itl(j) + sum(itl(i) = 1 to itl(j), itl(i) - 1)
    = sum(itl(i) = 1 to itl(j) + 1, itl(i) - 1)
    which establishes itl(H)(itl(j) + 1).

  2. Prove by induction that the value sps(itl(n), 2) - itl(n) is always even for any non-negative integer itl(n).

    Let the hypothesis be

    itl(H)(itl(n)) = sps(itl(n), 2) - itl(n) is even.
    The base case itl(H)(0) = sps(0, 2) - 0 = 0 is true. Let itl(H)(itl(j)) be true for itl(j) >= 0 and consider itl(H)(itl(j) + 1):
    sps((itl(j) + 1), 2) - (itl(j) + 1) = sps(itl(j), 2) + 2itl(j) + 1 - itl(j) - 1
    = sps(itl(j), 2) + itl(j)
    which is even by the inductive hypothesis.

  3. Use induction to design an algorithm for linear search: given the array itl(A) of objects and an object itl(x), return the index itl(i) at which itl(A)[itl(i)] = itl(x), or return -1 if itl(x) doesn't appear in itl(A).

    The hypothesis itl(H)(itl(n)) be a straightforward restatement of the problem:

    Either 0 <= itl(i) < itl(n) and itl(A)[itl(i)] = itl(x)
    or itl(i) = -1 and for all itl(j) such that 0 <= itl(j) < itl(n), itl(A)[itl(i)] != itl(x)
    for any itl(n)-element array itl(A).
    The base case itl(H)(0) is established by setting itl(i) to -1: itl(A) contains no elements at all.

    For the inductive step, assume itl(H)(itl(j)) is true and consider itl(H)(itl(j) + 1). Given an itl(j) + 1 element array, pick any from the array and compare it to itl(x). If they're equal, set itl(i) appropriately, otherwise continue searching through the rest of the array. Because the rest of the array has itl(j) elements, the inductive hypothesis holds and itl(i) will be set correctly.

    A linear search algorithm follows directly from the inductive argument; however, the argument selected an arbitrary element of itl(A) to examine, giving us a degree of freedom when developing the algorithm. Just to be different, the algorithm examines the middle element of itl(A). 

    int lsa(A, x)

  n <- |A|

  if n = 0
    return -1
  else
    m <- n/2
    if A[m] = x
      return m
    else
      return lsa(A[0..m-1] || A[m+1..n-1], x)
    where the || operator is array concatenation.

  4. Write down the binary search algorithm. Write down a loop invariant for your binary search algorithm. Use your loop invariant to prove your algorithm is correct.

    The binary search algorithm is 

    bool bsearch(a, x)

  l <- 0
  r <- |a|

  do l < r
    m <- l + (r - l)/2
    if a[m] <= x then l <- m + 1
    or x < a[m]  then r <- m
    fi
  od

  return l > 0 and a[l - 1] = x
    Binary search works by chopping the array in half and throwing away the half that can't contain the element being searched for. The invariant should reflect that behavior:
    a[0 .. l - 1] <= x and x < a[r .. |a| - 1] and l <= r
    In this case, the invariant partitions the array so that the search element, if it exists, is in the left part of the array.

    The initial assignments to l and r preserve the invariant because they both describe empty segments of a.

    Let the invariant be true when the loop body starts executing. Because l < r, the first assignment establishes l <= m < r. One of the two if branches must be true. If the first is true, extending the left part of the array to one past the element a[m] maintains the invariant; it also increases the value of l. If the second branch is true, extending the right part of the array to the element a[m] also maintains the invariant and decreases the value of r. In either case, executing the do body maintains the invariant.

    Because the value of l is increased or the value r is decreased on every iteration, eventually the do guard l < r will fail, in which case l >= r. Coupled with the invariant l <= r, this means that l = r, and all of a has been partitioned into two parts. If a contains x, it will be in the left part of itl(a), and, because itl(a) is sorted, it will be the right-most element.

This page last modified on 12 i2m(11) 1999. m4_dnl $Revision: 1.2 $, $Date: 1999/03/12 17:36:48 $ m4_divert(1) m4_changequote({, }) {m4_define(tblfcntnts, _toc_tableit(}_hdrs{) _toc_down(_toc_ilevel, _toc_level) ) m4_define(_toc_tableit, m4_regexp($1, \([0-9]+\) \([0-9]+\) \([^ ]+\) \(.*\), m4_ifdef(_toc_level, , m4_define(_toc_level, m4_eval(\2 - 1)) m4_define(_toc_ilevel, _toc_level)) _toc_entry(\1, \2, \3) _toc_tableit(\4)) ) m4_define(_toc_down, m4_ifelse(m4_eval($1 < $2), 1, _toc_down($1, m4_eval($2 - 1))) ) m4_define(_toc_entry, m4_ifelse(m4_eval($2 > _toc_level),1,