Chapter 2.3: The Stable Matching Problem w/Lists & Arrays

In chapter 1.1, we created a basic algorithm for the Stable Matching Problem without having to do any programming. We didn't have to do any actual programming in order to find the bound on run-time for this algorithm, however it is important to think about how the information is presented in a programming situation. Two basic data structures that would work well with our particular algorithm are lists and arrays. These data structures are optimized for certain functions and one structures strengths are another's weaknesses.

• Arrays: Can answer queries of the form “What is the ith element on the list?” and can determine whether a particular element, e, belongs to the list.
• Lists (linked): Good for inserting and deleting elements excessively.

In the Stable Matching Problem, we must be able to do each of these things in constant time:

1. Identify a single man
2. For a man, m: to identify the highest-ranked woman to whom he has not yet proposed
3. For a woman, w: to decide if she is currently engaged, and if so, to whom
4. For a woman, w, and two men, m and m': to decide which of m or m' is preferred by w.

In this situation, it would be best to keep the single men in a linked list, since men can go from being single to engaged (and back to single) several times throughout the algorithm; the dynamic size of a linked list works the best in this case. When a man becomes engaged, we can delete him from the list simply by reassigning the pointers around him (splicing him out). In order to keep up with current engagements, we can keep engaged pairs in an array, where the woman is the index and the man is the value at that index. This works best since once a woman becomes engaged, she stays that way throughout the remainder of the algorithm. In an array, reassigning values to keys can be done in constant time. The most difficult part comes when the woman, w, must decide between m and m'. Before the algorithm starts, we can create an n x n array, call it Ranking, where Ranking[w,m] contains the rank of man m in the sorted order of w's preferences. This array can be created in linear time. This way, to decide which man w prefers, we can just compare Ranking[w,m] with Ranking[w,m'] which can be done in constant time.

This section was very easy to read, especially after the lecture on this topic. I thought it was interesting that we were able to figure the running time out without actually implementing the algorithm. I honestly didn't even realize that we were just talking things out in class until I read this chapter and realized that we really haven't done any kind of program. So, in a way, this section was kind of like a proof of the work we've done in class. I'd rate this section a 10!