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 Homework 7 hdr(2, Homework 7 - Procedure and Data Correctness) hdr(3, CS 512, Algorithm Design)

  1. The function itl(f)(itl(i), itl(j)) is defined for all non-negative integers itl(i) and itl(j), and returns an integer. itl(f) is increasing in both arguments; that is itl(f)(itl(i), itl(j)) < itl(f)(itl(i) + 1, itl(j)) and itl(f)(itl(i), itl(j)) < itl(f)(itl(i), itl(j) + 1) for all valid arguments itl(i) and itl(j). Derive and prove correct an algorithm that accepts an integer itl(n) and returns the number of pairs (itl(i), itl(j)) for which itl(f)(itl(i), itl(j)) <= itl(n).

  2. A set of itl(n) cups are arranged in a circle. Each cup contains some positive number of beans. Derive and prove correct an algorithm that selects some contiguous subset of the cups having the property that the number of beans contained by the selected cups is as close to half of the total number of beans as possible.

    The difficult part of this problem is trying to figure out how to reduce the induction hyphothesis itl(H)(itl(j) + 1) to itl(H)(itl(j)). But before getting the that, we need to state the hyphothesis:

    itl(H')(itl(n)) - the algorithm itl(half)(itl(A)) can, given an array of itl(n) positive integers, find an arc of elements such that sum of the numbers in the arc is as close to half the sum of numbers in itl(A) as any other arc in itl(A).
    There is a problem with this hyphothesis, though. To establish the induction, we need to change a (itl(j) + 1)-element array into a itl(j)-element array by dropping an element. However, in doing so, we change the total sum of the elements in the array. It is not at all clear that finding an arc for a itl(j)-element array makes it possible to easily find an arc for the (itl(j) + 1)-element array because of the differences in the array sums.

    We could press ahead with itl(H')() and see what kind of trouble we encounter, but it seems more prudent to restate the hyphothesis in a slightly weaker form that avoids the difficulty:

    itl(H)(itl(n)) - the algorithm itl(half)(itl(A), itl(T)) can, given an array of itl(n) positive integers, find an arc of elements such that sum of the numbers in the arc is as close to itl(T) as any other arc in itl(A).
    It should be clear that itl(half)(itl(A), itl(sum(itl(A))/2)) solves the oritinal problem. itl(H)() is weaker than itl(H')() because itl(H)() admits a larger class of problems than does itl(H')(). itl(H)() avoids the difficulty with itl(H')() because it decouples the target number - half the sum of itl(A) - from the actual contents of itl(A), meaning we can change itl(A) by adding and removing element without changing the problem. Of course, we now have the obligation to demonstrate that the value of itl(T) doesn't change, or at least changes in acceptable ways

    If |itl(A)| = 0, then returning 0, or any constant value, establishes itl(H)(0).

    Suppose itl(H)()(j) is true for itl(j) >= 0 and consider itl(H)(itl(j) + 1).

This page last modified on 14 i2m(12) 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,