# Introduction to Software Design

Lately, we've been looking at the problem: Given an ADT specification, how do we choose data structures and algorithms to provide an efficient implementation? Now we turn to a higher-level question: Given a program specification, how do we choose appropriate ADT's to represent the information, how do we design appropriate algorithms to solve various parts of the problem, and how do we ensure that all the pieces of the implementation fit together to solve the given problem?

This task, known as software design, is not easy, but it can be a lot of fun. Although there are conventions, there are no rules cast in stone. In fact, software design is as much an art as it is a science. The best way to become good at design is to see a lot of designs, do a lot of designs, and develop in yourself an arsenal of design techniques and design patterns that will help you find ways to manage complexity in the design process.

We'll begin the discussion of software design with an interesting example problem known as "The Stable Marriage Problem."

## The Stable Marriage Problem

Consider the following information:
• a collection of eligible men, each with a rank ordered list of girlfriends
• a collection of eligible women, each with a rank ordered list of boyfriends
Assume that:
• the number of men and women are equal
• all men rank all women, and vice versa
• rank ordered lists are in decreasing order of preference
We define a marriage arrangement to be a pairing of the men and women such that
• each man is paired with one woman and
• every person appears in exactly one pair.
We say that a marriage arrangement is stable if there does not exist a woman X and man Y such that
• X prefers Y over X's husband, and
• Y prefers X over Y's wife.
(If there would exist such people, then they would want to run off together, creating an unstable situation.)

The problem is: Given the preference rankings of the men and women, construct a stable marriage arrangement.

Let's begin by thinking of an algorithm idea for solving the problem, and then work our way toward an implementation, considering how we could represent the information most naturally. This is sometimes called "top-down design."

High-level algorithm idea (in pseudocode):

while there are still eligible men
match an eligible man to the highest ranked woman on his list who'll have him.

We say "who'll have him" because some women ranked high on his list may already be engaged to people they prefer over him.

So far so good, but how do we do the matching? Here's an idea:

Given an eligible man M
let M propose to the most preferred woman W on his list
if W accepts the proposal
W's current engagement (if any) is broken and her old fiance is again eligible.
W shortens her list to include only those ranked above M
M removes W from his list (but keeps the rest in case she dumps him)
M and W become engaged, making M no longer eligible
if W rejects the proposal
M removes W from his list
Note: In the case of rejection, a match isn't made, but M remains eligible so he'll get a chance to make another proposal.

Now things are becoming clearer, but how does a woman decide whether to accept a proposal? Let's say she accepts if he's on her list. (If someone better comes along later, she can always dump him!)

How do we know the final arrangement will be stable? Well, suppose there exists a man Y and woman X such that they prefer each other over their own spouses. Since Y prefers X over his own spouse, then he must have proposed to her before proposing to his own spouse. So there are two possibilities of what happened at the time of that proposal. Either

1. X rejected Y, which means that she was already engaged to someone she preferred over Y (she had scratched Y off her list). Therefore, she must either be married to that person or someone else who was on her list at the time of the proposal. Therefore, she could not prefer Y to her own spouse, contradicting our assumption.
2. X accepted Y, but dumped him later. Since she would have dumped him only in order to become engaged to someone higher ranked on her list, she must not prefer Y over her own spouse, again contradicting the assumption.

In both cases, the assumption is contradicted. So, there cannot exist a man Y and woman X such that they prefer each other over their own spouses. Therefore, the arrangement is stable.

How do we know everyone gets paired off? Since the number of men and women are equal, the only way for a man to remain eligible at the end is for there to be an unengaged woman who rejects him. However, the only rejections come from women who are engaged.

Before proceeding too much further, we need to choose ADT's to hold the relevant information. Let's think about what happens as the algorithm runs. At any point in the algorithm:

• a man is either eligible or engaged
• a woman is engaged to at most one man
• each man and woman has a ranked list of preferences

For eligible men, we can use a list of men. For the engagements, we can use a mapping from women to men. Each man and woman can be an object that contains a list of preferences.

Who gets a better deal in this algorithm, the men or the women? It turns out that since the unengaged women in this algorithm accept any proposal, the men end up happier on average.

For example, suppose there are 5 men and 5 women, and suppose every man has a different first choice. Then they'll all get their first choice, regardless of the preferences of the woman.

Maybe there's a lesson here?

Anyway, this algorithm is used every year to match graduating medical students to hospitals. The hospitals play the role of the men. We're not aware of it actually being used to arrange marriages, however.

The main procedure for the algorithm thus becomes:

```
public static void findMarriages() {

while (eligible != null) {

Man m = (Man) eligible.person;

Woman w = m.topPick();

if (w.likes(m)) {

Man oldHusband = (Man) couples.lookup(w);

if (oldHusband == null)

eligible = eligible.next;

else

eligible = new PersonList(oldHusband, eligible.next);

couples.map(w, m);

w.trimList(m);

}

m.scratchTop();

}

}

```
The complete implementation is available under the example code page:
Kenneth J. Goldman
Last modified: Sun Apr 20 23:16:20 CDT 1997