Solutions to Exercises of HW 5

  1. Greedy:

    A Greedy algorithm for making change given denominations in decreasing order and an amount B to sum to:

       0. Set T := emptyset
       1. Construct a list of weighted objects as follows: 
          starting with L equal to the emptylist, add (d1/B)+1 
          objects of weight d1, then append (d2/B)+1 objects 
          of weight d2 and so on for all denominations.
       2. Repeat the following until L is empty:
       3.    Let e :=pop L
       4.    If objects of T U {e} sum to no greater than B Set T := T U {e}
       5. Return T as a solution: use coins of denominations of T in numbers
          given in T.

    Correctness is proven by showing that, with the right weights on objects (coins), this can be rewritten as a matroid problem where the objective is to find a maximal independent set of least weight. For the matroid, let a subset of coin objects be an independent set if and only if its sum cannot be obtained by fewer coins. Check the properties:

    1. If I1={a,b,c...} is an independent set then so is any subset of I1.

      Let I2 be a subset of I1 with sum C and suppose I3 also sums to C with fewer objects than I2. Then the set (I1 \ I2) U I3 has fewer objects than I1 but the same sum, so I1 could not have been an independent set, a contradiction. Therefore, any subset of an independent set contains the minimum number of coins which achieves its sum and must be an independent set.

    2. If I1 and I2 are independent sets with |I2|=|I1|+1 then there is an object e in I2 such that I1 U {e} is an independent set.

      Observe, this may not generally be satisfied for two reasons. First, obviously, if the denomination 1 is missing. Second, for example, if coin denominations are 9,8,6,5,3,2,1 then sets of coins with the following denominations {6,5,5} and {5,2} are supposed to be independent sets, by the definition above, since at least three coins must be used to total 16 and two must be used to total 7. But taking a coin of denomination 5 from the first set and sticking into the second gives {5,5,2} which sums to 12, a sum which can be achieved by {9,3}, and taking 6 from the first set and adding to the second gives {6,5,2} which sums to 13, a sum which can be achieved by {8,5}. This means, for this set of denominations, there is at least one set, namely {5,2}, which should be an independent set, by definition, but cannot be an indendent set by consequence of failure of property 2. This answers the third part of the first question, by the way.

    Thus, we need to show that property 2 is satisfied using USA coin denominations 1,5,10,25,50. Of course, there is a 1 in the denomination list so we only have to be concerned about examples such as the one above. Let be denominations. Let

       a1*d1 + ... + ak*dk = B
    be the sum of the coin values in the minimal solution given B where ai is the number of coins of denomination di. Examples above can occur only if adding 1 to one of the ai results in a new sum of coin values for which there is a minimal solution. That is,
       b1*d1 + ... + bk*dk = B'
    and, from before,
       a1*d1 + ... + (ai+1)*di + ... + ak*dk = B'
    where we added 1 to ai. But bi must be 0 or else there is a smaller set summing to B than the a set. Also 1*di is not a multiple of any other dj no greater than bj since that would mean the b set is not minimal (combine at least two of the dj to get a single di). This means multiples of at least two denominations other than dj must sum to 1*di but not in such a way that they can combine to reduce the total of the multipliers. Checking 1,5,10,25,50 shows this is not possible. So the second matroid property holds for this set of denominations.

    All that remains is to choose weights for the objects (coins) that maximize the total weight of the maximum size independent set. Just set the weight of a coin object to its value minus 1. Then, the maximum value of the maximal independent set will be B minus the smallest number of coins used.

    Now, consider the denominations 1,c1,...,ck where c and k are integers. The sum a0*1 + ... + ai*ci must have ai < c or else there is a smaller set summing to the same total. But then the sum is no greater than

       (c-1)(1+c1+...+ci) = (c-1)*(ci+1-1)/(c-1) < ci+1
    so the second matroid property holds and the greedy method applies.

  2. Maximum Number of Interchanges:

    Occurs when interchanging two outside numbers in a reverse ordered list.

       n, n-1, n-1, ... , 3, 2, 1
       1, n-1, n-2, ... , 3, 2, n
    The reduction in the number of inversions is 2*(n-2)+1. This is important because some sorts compare adjacent elements only and in that case the number of inversions may decrease by at most 1.

  3. Search the Ordered List:

       Set index = 1
       Repeat the following until the index is found or index is greater than n
          If L[index] equals X then return index
          Set index = abs(L[index]-X)+index
       Return "no index found"