We have to think about how the data will be represented and manipulated in an implementation of the algorithm in order to analyze the running time of an algorithm expressed in a high-level fashion. Keep in mind: G-S algorithm terminates in at most (n^2) iterations, and our implementation provides a corresponding worst-case running time of O(n^2), counting actual computational steps rather than simply the total number of iterations.

To attain such a bound, we only need to use two data structures: lists and arrays. In a Stable Matching problem, each man and each woman has a ranking of all members of the opposite gender. We have to ask ourselves which data structures we will use to implement the following:

* How will such a ranking be represented? * Which men and women are free as the algorithm maintains a matching? * Who is matched or engaged with whom?

An algorithm designer choses data structures that make it efficient and easy to implement for their algorithm. In some cases this may involve preprocessing the input to convert it from its given input representation into a data structure that is more appropriate for the problem being solved.

Arrays and Lists

*Focus on a single list, such a s the list of women in order of preference by a single man. Maybe we can use an array A of length n to keep a list of n elements???

Properties of an Array

1. Accessing the ith element??? O(1)
2. Find an element in an array??? We need to check elements one by one in O(n) time, order is assumed to be unknown.
3. If array is sorted? What is the cost of finding if an element e is in the array??? O(log n) using a binary search.

An array is less good for dynamically maintaining a list of elements that changes over time, such as the list of free men in the Stable Matching algorithm; since men go from being free to engaged, and potentially back again. A list of free men needs to grow and shrink during the execution of the algorithm. This is difficult to implement with an array.

Alternatively, to maintain such a dynamic set of elements, we shall use a linked list. A linked list uses pointers that point from the first element to the second and so on. Starting at the first element, we can traverse the entire list in time proportional to its length.

Implementing a Doubly linked list, we need two pointers and two fields: First and Last that point to the first and last elements respectively, and fields element.Next and element.Prev to know which elements precede and proceed a record (element). Inserting and Deleting an element to a doubly linked list (“splicing it in” and “splicing it out”) Figure 2.1 on Page 45 shows how the two modifications can be made.

While lists are better than arrays in maintaining dynamic changing sets, they also have disadvantages. We cannot find the ith element of the list in O(1) time, we have to traverse the whole list which takes a total of O(i) time.

Given all the relative advantages and disadvantages of arrays and lists, we are able to convert a problem's input from one format to another. In this case it would cost us O(n) time (between arrays and lists). This helps us to freely choose the data structure that suits the algorithm better and not be constrained by the way the information is given.

Implementing the Stable Matching algorithm

Its upper bound running time is O(n^2), thus we need to be able to implement each iteration in constant time.

• N men ,and N women, ordered (say, alphabetically) and associate number i with the ith man or ith woman. This allows us to define an array indexed by all men or all women.
• A preference list for each ma and each woman. We need two arrays one for each. We will use ManPref[m,i] to denote the ith woman on man's preference list. This is also similar t any woman's pref list, WomanPref[w,i], i being the ith man on her prefernece list. the total amount of memory needed to give the preferences for all 2n individuals is O(n^2), as each person has a list of length n.

4 steps of the algorithm we need to do in constant time:

1. Identify a free man
2. Man identifies highest-ranked woman he has to propose to next
3. if woman is engaged, identify her partner
4. partner or man who just proposed? (But can we maintain a woman's pref list? ) –> we would have to build an auxiliary data structure at the beginning.

Create an n * n array Ranking, that contains the rank of man in the sorted order of w's preferences. This way comparisons can be made in constant time. Rankings[w,m] vs Rankings[w,m prime].

After all, we acknowledge that the data structures described above allow us to implement the GS algorithm in O(n^2) time.

This section was readable but long, had a trouble a few times analyzing whats going on in steps. Scale: 8/10.