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 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):
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:
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
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:
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: