Given n men and n women and each of their preference lists, I described the Gale-Shapley algorithm as follows: Initially all men and women are free and M is an empty matching. While some man m is free let w be the first woman that has not rejected him If w is free match m to w; m and w are no longer free Else let m0 be the man w is currently matched to if w prefers m to m0 w rejects m0 and m0 becomes free match m to w and m is no longer free else w rejects m and m remains free Endwhile Add all the pairs to M and return M. To analyze the running time of this algorithm, we need to be more specific. Let the men be m1, m2, . . . , mn and the women be w1, w2, . . . , wn. So assume that P is the matrix that describes the preferences of the men. Specifically, let its rows and columns be indexed from 1 to n so that P[i][j] = r if the jth choice of mi is wr. Similarly, let Q[i][j] denote the jth choice of wi . For example, when n = 3, the input can look like this:

P is equal to matrix

1 2 3

1 3 2

1 2 3 and Q =

2 1 3

2 1 3

1 2 3

For this problem, (i) Come up with an implementation for the algorithm above. That is, specify how you will keep track of which men and women are free, how you will find the first woman that has not rejected a man, etc. You may want to, for example, define some variables, introduce some data structures, etc.

(ii) Determine the running time of your implementation in terms of n. Remember that the input consists of the preference lists of the n men and n women. Do you think you have the best possible implementation? Why?