CS 512 Homework 6

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

A bank owns a set of itl(n) branches. Every Saturday afternoon, two armored cars go to all the branches, pick up the money collected in the past week, and bring the money back to the central vault. For security reasons, total amount of money picked up by each armored car should be equal if possible. Assuming you know the amount of money to be picked up at each bank branch, come up with an algorithm for finding two routes, one for each car, such that the the total amount of money picked up by each car is the same. If no such pair of routes exists, your algorithm should indicate that and stop.
You should assume that each bank branch is visited by exactly one car each week, that all branches are visited each week, and that each car picks up all available money at each branch. You may also assume that it's possible to directly drive from one branch to another.
This problem is easiest solved by reducing it to the set partition problem. Given a set of itl(n) banks, each of which having sbs(itl(d), itl(i)) dollars at the end of the week, 1 <= itl(i) <= itl(n), form the set itl(S) = {sbs(itl(d), 1), sbs(itl(d), 2), ..., sbs(itl(d), itl(n))}. If the banks' weekly take can be split evenly as described above, then itl(S) can be partitioned into two equal parts. If itl(S) can be partitioned into two equal parts, then the banks' weekly take can be split evenly also. The reduction from the bank problem to the set partition problem preserves correctness, and the set partition problem can be used to solve the bank problem.
The set itl(S) would actually be more likely defined as {(1, sbs(itl(d), 1)), (2, sbs(itl(d), 2)), ... (itl(n), sbs(itl(d), itl(n)))}. Not only does this definition of itl(S) enable the algorithm to keep track of the banks, it eliminates the problems that occur when sbs(itl(d), itl(i)) = sbs(itl(d), itl(j)) and itl(i) != itl(j).
You work for a company that installs fire detectors and smoke alarms. There is one type of fire detector and two types of smoke alarms: optical and ionic. To properly protect a house, each room must have one device; for maximum sensitivity, when two rooms are connected by a door, each room should have a different device (the two types of smoke alarms are different from one another, and a fire detector is different from either type of smoke alarm).
Your job is to derive an algorithm that determines how to assign detection devices to rooms so that the house is properly protected with maximum sensitivity, or to indicate that no such assignment is possible.
This problem is easiest solved by reducing it to the three-color problem. Represent a house as a graph in the following way: each vertex in the graph represents a room in the house (stairways and halls are taken as rooms). Two vertices are connected by an edge in the graph if and only if the associated rooms in the house are directly connected by a doorway. Suppose there is an assignment of detectors to rooms in a house such that it is possible to achieve maximum sensitivity. Then there exists an analogous assignment of colors to vertices such that the three-color problem is solved. In the other direction, suppose there exists a solution to the three-color problem. Then we can use the three coloring to assign devices to rooms to achieve maximum sensitivity.
A contiguous subsequence of a word is alphabetical if the letters in the subsequence appear in alphabetical order. For example, given the word itl(knapsack), the subsequence itl(ack) is alphabetical because the letters itl(a), itl(c), and itl(k) are in alphabetical order. The subsequence itl(nack) is not alphabetical because itl(n) is not contiguous with itl(ack) in itl(knapsack); itl(sack) is not alphabetical because the letters itl(s) and itl(a) are not in alphabetical order.
Design and prove correct an algorithm that accepts a word and finds the largest alphabetical contiguous subsequence in the word. Your algorithm should take time proportional to the length of the input word. You may assume words contain only the letters itl(a) through itl(z) and that case doesn't matter.
Let's bring induction to bear on this problem by using the hypothesis
itl(H)(itl(n)) - the algorithm find_las() can find the largest alphabetical contiguous subsequence in a word of itl(n) letters.
itl(H)(itl(1)) is immediately true because any word of one letter is the largest alphabetical contiguous subsequence in the word. Assume itl(H)(itl(j)) is true for some itl(j) >= 1 and consider itl(H)(itl(j) + 1). A word of itl(j) + 1 letters can be reduced to a word of itl(j) letters by removing one of the letters, but which one?
The algorithm is interested in contiguous subsequences, so removing a letter from the middle of the word, because it creates more non-contiguous pieces, appears to lead to more work than would removing a letter from either end of the word. The problem statement has no implicit or explicit sense of direction, so removing a letter from either end appears acceptable; take the letter from the right end of the word.
Given that the algorithm can find the largest alphabetical contiguous subsequence in a word of itl(j) letters, how can the algorithm deal with the word with itl(j) + 1 letters formed by adding a new letter to the right? Adding a new letter effects the word by changing the alphabetical contiguous subsequence that ends at the right end of the word. The change occurs in one of two ways: either the letter extends the subsequence by one, or the letter starts a new subsequence ending at the right. If the right subsequence is extended, it may now be larger than the largest subsequence; otherwise the right subsequence has no direct influence on the largest subsequence.
Before going on to the algorithm, the hypothesis needs to be strengthened to include the right-most contiguous subsequence:
itl(H)'(itl(n)) - the algorithm find_las() can find both the largest alphabetical contiguous subsequence in a word of itl(n) letters and the largest alphabetical contiguous subsequence ending at the rightmost letter in the word.
The base case itl(H)'(1) is again easy to establish, and the inductive case itl(H)'(itl(j) + 1) given itl(H)'(itl(j)) for itl(j) >= 1 follows from the discussion in the previous paragraph. The algorithm proper is
```
int find_las(a)

  max_start <- 0
  max_length <- 0
  right_start <- 0
  right_length <- 1

  i <- 1
  do i < |a|
    if a[i - 1] <= a[i]
      right_length <- right_length + 1
    or a[i - 1] > a[i]
      right_start = i
      right_length = 1
    fi
    if right_length > max_length
      max_start <- right_start
      max_length <- right_length
    fi
    i <- i + 1
  od

  return max_start
```
See Section 5.8 in the text for a discussion of a similar problem.
Design and prove correct an algorithm that accepts an array of boolean values and returns the decimal value of the array when interpreted as a binary number (the leftmost boolean value at index 0 is the most significant bit of the binary number). You may assume all numbers are non-negative, and you need not worry about overflows.
Let's appeal once again to induction by using the hypothesis
itl(H)(itl(n)) - the algorithm b2d() returns the decimal equivalent of an itl(n) bit binary number.
Assume an itl(n)-bit binary number is represented by an itl(n)-element boolean array itl(b) with the left-most element - that is itl(b)[0] - being the most significant bit and the right-most element - that is, itl(b)[|itl(b)| - 1] - being the least significant bit. b2d() can satisfy itl(H)(itl(0)) by returning 0. Assume b2d() satisfies itl(H)(itl(j)) for some itl(j) >= 0 and consider itl(H)(itl(j) + 1).
A (itl(j) + 1)-bit binary number can be reduced to a itl(j)-bit binary number removing one of the bits. Removing the right-most, least significant bit gives b2d(b[0..j]) = b2d(b[0..j-1])*2 + b[j], which we can establish as being true using the induction hypothesis and the definition of binary numbers. Removing the left-most, most significant bit gives b2d(b[0..j]) = b[0]*sps(2, j) + b2d(b[1..j]), which we can also establish using the induction hypothesis and the definition of binary numbers. Removing a bit from somewhere else in the binary number is also possible, but too complicated to think about.
The algorithm follows immediately, removing the right-most bit:
```
int b2d(bits)

  l = |bits| - 1
  if l = -1
    return 0
  else
    return b2d(bits[0..l - 1])*2 + bits[l]
  
```
See Section 2.12 in the text for a discussion of a similar problem.

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,

m4_translit($2, , ,) ) }