Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:virginia:chapter1 [2012/01/17 23:29] – lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter1 [2012/01/23 21:38] (current) – [Section 1: Stable Matching] lovellv
@@ Line 6: / Line 6: @@
 In this section, our goal is to find an algorithm that generates a perfect, stable matching between n men and n women.  The Gale-Shapley algorithm accomplishes this.
-Algorithm outline: Pick a random man and have him propose to his top choice who he has not yet proposed to.  This woman will accept if single or if this man is preferred to her current mate.  Otherwise he remains single.  Repeat this until every man is engaged or has proposed to every woman.
+Algorithm outline (p 6): Pick a random man and have him propose to his top choice who he has not yet proposed to.  This woman will accept if single or if this man is preferred to her current mate.  Otherwise he remains single.  Repeat this until every man is engaged or has proposed to every woman.
 We found the maximum number of iterations for this algorithm is n^2 and that each execution produces the same set of pairs.  Since the men propose, they end up with their best possible match.