CIT 594 Assignment 7: Dating service clarifications Spring 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 `k2` times longer, then comparisons are the wrong choice for a characteristic operation.

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.