HW 5 - Solutions

Solutions to Exercises of HW 5

Greedy:
A Greedy algorithm for making change given denominations d₁...d_k 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 (d₁/B)+1 
      objects of weight d₁, then append (d₂/B)+1 objects 
      of weight d₂ 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 I₁={a,b,c...} is an independent set then so is any subset of I₁.
  Let I₂ be a subset of I₁ with sum C and suppose I₃ also sums to C with fewer objects than I₂. Then the set (I₁ \ I₂) U I₃ has fewer objects than I₁ but the same sum, so I₁ 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 I₁ and I₂ are independent sets with |I₂|=|I₁|+1 then there is an object e in I₂ such that I₁ 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 d₁...d_k be denominations. Let
```
   a₁*d₁ + ... + a_k*d_k = B
```
be the sum of the coin values in the minimal solution given B where a_i is the number of coins of denomination d_i. Examples above can occur only if adding 1 to one of the a_i results in a new sum of coin values for which there is a minimal solution. That is,
```
   b₁*d₁ + ... + b_k*d_k = B'
```
and, from before,
```
   a₁*d₁ + ... + (a_i+1)*d_i + ... + a_k*d_k = B'
```
where we added 1 to a_i. But b_i must be 0 or else there is a smaller set summing to B than the a set. Also 1*d_i is not a multiple of any other d_j no greater than b_j since that would mean the b set is not minimal (combine at least two of the d_j to get a single d_i). This means multiples of at least two denominations other than d_j must sum to 1*d_i 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,c¹,...,c^k where c and k are integers. The sum a₀*1 + ... + a_i*cⁱ must have a_i < c or else there is a smaller set summing to the same total. But then the sum is no greater than
```
   (c-1)(1+c¹+...+cⁱ) = (c-1)*(cⁱ⁺¹-1)/(c-1) < cⁱ⁺¹
```
so the second matroid property holds and the greedy method applies.
Maximum Number of Interchanges:
Occurs when interchanging two outside numbers in a reverse ordered list.
Before:
```
   n, n-1, n-1, ... , 3, 2, 1
```
After:
```
   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.

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"