**Greedy**:A Greedy algorithm for making change given denominations

`d`in decreasing order and an amount_{1}...d_{k}`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`objects of weight_{1}/B)+1`d`, then append_{1}`(d`objects of weight_{2}/B)+1`d`and so on for all denominations. 2. Repeat the following until_{2}`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:

*If*`I`is an independent set then so is any subset of_{1}={a,b,c...}`I`._{1}Let

`I`be a subset of_{2}`I`with sum_{1}`C`and suppose`I`also sums to_{3}`C`with fewer objects than`I`. Then the set_{2}`(I`has fewer objects than_{1}\ I_{2}) U I_{3}`I`but the same sum, so_{1}`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._{1}*If*`I`and_{1}`I`are independent sets with_{2}`|I`then there is an object_{2}|=|I_{1}|+1`e`in`I`such that_{2}`I`is an independent set._{1}U {e}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`be denominations. Let_{1}...d_{k}a

be the sum of the coin values in the minimal solution given_{1}*d_{1}+ ... + a_{k}*d_{k}= B`B`where`a`is the number of coins of denomination_{i}`d`. Examples above can occur_{i}*only if*adding 1 to one of the`a`results in a new sum of coin values for which there is a minimal solution. That is,_{i}b

and, from before,_{1}*d_{1}+ ... + b_{k}*d_{k}= B'a

where we added 1 to_{1}*d_{1}+ ... + (a_{i}+1)*d_{i}+ ... + a_{k}*d_{k}= B'`a`. But_{i}`b`must be 0 or else there is a smaller set summing to_{i}`B`than the`a`set. Also`1*d`is not a multiple of any other_{i}`d`no greater than_{j}`b`since that would mean the_{j}`b`set is not minimal (combine at least two of the`d`to get a single_{j}`d`). This means multiples of at least two denominations other than_{i}`d`must sum to_{j}`1*d`but not in such a way that they can combine to reduce the total of the multipliers. Checking_{i}`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`where^{1},...,c^{k}`c`and`k`are integers. The sum`a`must have_{0}*1 + ... + a_{i}*c^{i}`a`or else there is a smaller set summing to the same total. But then the sum is no greater than_{i}< c(c-1)(1+c

so the second matroid property holds and the greedy method applies.^{1}+...+c^{i}) = (c-1)*(c^{i+1}-1)/(c-1) < c^{i+1}**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"