CIT 594 Assignment 7: Dating service clarificationsSpring 2004, David Matuszek |

**Average happiness:**

If you have `w`

women and `m`

men, your average happiness
should be

`(Total happiness for all couples) / (minimum of w and m)`

For example, if you have `3`

women and `5`

men, and your
couples have happiness values `90`

, `80`

, and `70`

,
then your average happiness should be `(90 + 80 + 70) / 3 = 80`

Count a happiness value once for each couple (not once for each person).

If you match up as many couples as possible, ignore the unhappiness of people who don't get a date.

If you don't make as many couples as possible--for example, if you have `3`

women and `5`

men, and you only form two couples--then you should
still divide by `3`

, which is the number of couples you *could*
make. As the problem is given, there isn't any reason to make fewer than the
maximum number of couples (this might be different if we had negative compatibility
values!).

**Characteristic operations:**

See my slides on Analysis of Algorithms.

A characteristic operation is something in your code that:

- you can count, and
- takes
`O(1)`

time (time bounded by a constant), and - is linearly related to the running time.

For example, if you are sorting an array, you might use the number of comparisons.
Each comparison takes a constant amount of time. If data that requires `k`

times as many comparisons also runs `k`

times longer, then comparisons
are a good choice for a characteristic operation. If data that requires `k`

times as many comparisons runs `k`

times longer,
then comparisons are the wrong choice for a characteristic operation.^{2}

If, for input of size `n`

, your program takes `O(f(n))`

running time, what this means is that your characteristic operation will be
executed` f(n)`

times (ignoring assorted constants).

To figure out what would make a good characteristic operation, you need to figure out what part of your program is most important in determining how long your program will take, as a function of the size of the input. Usually this is whatever is happening in the innermost loop of your program, that is, whatever is being done most often. For example:

int characteristicOperationCount = 0; public static void makeChange(int[] coins, int differentCoins, int maxChange, int[] coinsUsed, int[] lastCoin) { coinsUsed[0] = 0; lastCoin[0] = 1; for (int cents = 1; cents < maxChange; cents++) { int minCoins = cents; int newCoin = 1; for (int j = 0; j < differentCoins; j++){characteristicOperationCount++;if (coins[j] > cents) continue; if (coinsUsed[cents – coins[j]] + 1 < minCoins) { minCoins = coinsUsed[cents – coins[j]] + 1; newCoin = coins[j];}} coinsUsed[cents] = minCoins; lastCoin[cents] = newCoin; } }

In this code, the innermost loop is boldface, and this is where I have put (in red) a counter for characteristic operations. It's a little difficult to put this "characteristic operation" into words, but that's not important. If this is where the most work is being done, this is all the counting that needs to take place.