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

  1. Reduce the set partition problem to an integer linear programming problem.

    The set partition problem accepts a set of numbers itl(S) and returns true if there exists two sets itl(S1) and itl(S2) such that

    1. itl(S1) and itl(S2) are subsets of itl(S),
    2. union(itl(S1), itl(S2)) = itl(S),
    3. intersection(itl(S1), itl(S2)) = the empty set, and
    4. sum(itl(S1)) = sum(itl(S2))

    Given a particular instance of the set partition problem with itl(S) = {sbsin(v, 1), sbsin(v, 2), ..., sbs(itl(v), itl(n))}, we can form an integer linear programming problem as follows:

    1. The objective function is
      itl(c)(x) = sum(itl(i) = 1 to itl(n), sbs(itl(v), itl(i))sbs(itl(x), itl(i)))
      Because this is an integer linear program, each sbs(itl(x), itl(i)) is an integer.

    2. The equality constraint
      sum(itl(i) = 1 to itl(n), sbs(itl(v), itl(i))sbs(itl(x), itl(i))) = sum(itl(S))/2
      makes sure the solution isn't optimized past the point of equal subsets.

    3. The itl(n) nonnegative constraints sbs(itl(x), itl(i)) >= 0 and the itl(n) inequality constraints sbs(itl(x), itl(i)) <= 1 insures the integer sbs(itl(x), itl(i)) is either 0 or 1
    If the set itl(S) can be partitioned into two equal subsets, then the associated integer programming problem can be solved by picking one of the two subsets and letting sbs(itl(x), itl(i)) be 1 if sbs(itl(v), itl(i)) is in the subset or zero otherwise. Such an assignment to x satisfies all constraints.

    In the other direction, if the integer programming problem can be solved, form the subsets itl(S1) = { sbs(itl(v), itl(i)) such that sbs(itl(x), itl(i)) is 1 } and itl(S2) = itl(S) - itl(S1). itl(S1) and itl(S2) are disjoint and combine to form itl(S); because of the equality constraint, sum(itl(S1)) = sum(itl(S))/2, which means that sum(itl(S2)) = sum(itl(S))/2 and itl(S1) and itl(S2) form a partition of itl(S).

  2. The two-coloring problem accepts as input an undirected graph and returns true if each vertex can be assigned one of two colors such that every edge in the graph connects vertices of differ colors. A colleague of yours believes the two-color problem can be reduced to the three-color problem, and offers up the following justification: if itl(G) can be two colored, then it certainly can be three colored, so a three-color solution for itl(G) implies a two-color solution also. Is you college right or wrong? Explain.

    Your colleague is wrong. Your college failed to indicate how a three-color solution for itl(G) can be transformed into a two-color solution. A little thought shows that such a transformation can't exist: the graph consisting of three vertices connected as a triangle can be three colored, but it can't be two colored.

  3. A contiguous subsequence of a word is zig-zag alphabetical if it can be split into two consecutive alphabetical sequences. For example, the sequence itl(xyzabc) is zig-zag alphabetical because it consists of the two alphabetical sequences itl(abc) and itl(xyz). The sequence itl(axbyzc) is not zig-zag alphabetical because it can't be split into two alphabetical sequences.

    Suppose you want to use induction to derive an algorithm for finding the largest zig-zag alphabetical sequence in a given input word. What does your inductive hypothesis look like? Do not derive the algorithm itself, just the inductive hypothesis. Make sure you argue for the correctness of your hypothesis.

    Before going after the hypothesis, it will be helpful to observe that an alphabetical sequence is zig-zag alphabetical because it can be broken into two alphabetical sequences (for example, itl(abclmn) can be broken into itl(ab) and itl(clmn)). However, because the problem is looking for largest zig-zag alphabetical sequences, there's no advantage to breaking an alphabetical sequence into pieces. That means the hypothesis involves largest alphabetical sequences, which means this hypothesis should be related to the hypothesis for the homework problem.

    A second helpful observation is that a largest zig-zag alphabetical sequence must be made up of two adjacent largest alphabetical sequences. If the zig-zag alphabetical sequence contained more than two alphabetical sequences, they must be separated by a third alphabetical sequence, which violates the definition of zig-zag alphabetic; for example itl(xyzma) can be broken into the maximal alphabetical sequences itl(xyz), itl(m) and itl(a), so itl(xyzma) isn't zig-zag alphabetical.

    From the homework, the hypothesis for largest alphabetical sequences is

    the algorithm can find both the largest alphabetical subsequence in a word letters and the largest alphabetical subsequence ending at the rightmost letter in the word.
    The hypothesis needs to be changed to deal with zig-zag alphabetic sequences. The second observation suggests the hypothesis needs to be changed to keep track of the largest alphabetical sequence immediately adjacent to the right-most one, leading to the following hypothesis:
    itl(H)(itl(n)) - Given a word itl(w) with itl(n) characters, the itl(find_mzas)() algorithm can find

    1. The largest zig-zag alphabetical sequence in itl(w),
    2. the largest alphabetical sequence ending at the right-most character in itl(w), and
    3. the largest alphabetic sequence immediately adjacent to the largest right-most sequence in itl(w); from the second observation, this is equivalent to saying the largest zig-zag sequence ending at the right-most character in itl(w).

    A single character word establishes the base case itl(H)(1) because

    1. the word can be thought of as being followed (or preceded) by the empty sequence, which is an alphabetic sequence, so the word is the maximal zig-zag alphabetic sequence

    2. the word itself is the largest right-most alphabetical sequence in the word

    3. for the same reasons given in 1), the word itself is also the largest rightmost zig-zag alphabetical sequence in the word

    Note that the empty word containing no characters also establishes the base case itl(H)(0).

    For the inductive step, let itl(H)(itl(j)) be true for some itl(j) >= 1 and consider itl(H)(itl(j) + 1). Removing the right-most character from a (itl(j) + 1)-character word itl(w) leaves a itl(j)-character word itl(w)', and the inductive hypothesis holds for itl(w)'. There are two cases to consider based on the relation between itl(w)[itl(j) - 1] and itl(w)[itl(j)]:

    Because itl(H)(itl(j) + 1) holds for either case, and the cases are exhaustive, itl(H)(itl(j) + 1) is true.

  4. The function itl(pow)(itl(x), itl(n)) computes spsii(x, n). The repeated multiplication algorithm for implementing itl(pow)() multiplies 1 by itl(x) itl(n) times. Derive the inductive hypothesis for the repeated multiplication algorithm. Do not derive the algorithm itself, just the inductive hypothesis. Make sure you argue for the correctness of your hypothesis.

    The inductive hypothesis is

    itl(H)(itl(n)) - the algorithm itl(rma)(itl(x)), itl(n) multiplies 1 by itl(x) itl(n) times.
    If itl(rma)() returns 1 when itl(n) = 0, then itl(H)(itl(0)) is satisfied. Assume itl(rma)() satisfies itl(H)(itl(j)) for some itl(j) >= 0 and consider itl(H)(itl(j) + 1). We need to show that itl(rma)(itl(n), itl(j + 1)) computes sps(itl(x), itl(j) + 1).
    sps(itl(x), itl(j) + 1) = spsii(x, j)*x definition of exponentiation
    = itl(rma)(itl(x), itl(j))*x the inductive hypothesis itl(H)(itl(j)) holds
    = itl(rma)(itl(x), itl(j) + 1) definition of itl(rma)()

This page last modified on 3 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,