Differences

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

--- courses:cs211:winter2018:journals:goldm:ch1 [2018/01/17 00:11] – created goldm
+++ courses:cs211:winter2018:journals:goldm:ch1 [2018/01/17 00:18] (current) – goldm
@@ Line 1: / Line 1: @@
-    This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: "Could one design a college admissions process, or a job recruiting process, that was
+This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: "Could one design a college admissions process, or a job recruiting process, that was
 self-enforcing?" This algorithm can also be illustrated by matching groups of people into "couples" so that they all are matched with the best possible individual to lead to a stable relationship environment. The remainder of the section goes on to discuss implementation and results of the algorithm and related proofs which will be discussed after this summary.
-    As aforementioned, the motivation for the problem is to develop a college admissions/job recruitment process that self-enforced and avoided people "jumping ship" to other opportunities.
+As aforementioned, the motivation for the problem is to develop a college admissions/job recruitment process that self-enforced and avoided people "jumping ship" to other opportunities.
     Here is a sketch of the algorithm as given by the text:
     Initially all m E M and w E W are free
-While there is a man m who is free and hasn’t proposed to
+    While there is a man m who is free and hasn’t proposed to
-every woman
+    every woman
      Choose such a man m
      Let w be the highest-ranked woman in m’s preference list
-to whom m has not yet proposed
+     to whom m has not yet proposed
-     If ~ is free then
+     If w is free then
-(m, ~) become engaged
+     (m, w) become engaged
-     Else ~ is currently engaged to m’
+     Else w is currently engaged to m’
-        If ~ prefers m’ to m then
+        If w prefers m’ to m then
        m remains free
         Else w prefers m to m’
-(m,~) become engaged
+    (m,w) become engaged
-nlI becomes free
+    m' becomes free
         Endif
     Endif
-Endwhile
+   Endwhile
-Return the set S of engaged pairs
+  Return the set S of engaged pairs
+The algorithm runs in n squared.
+I found the discussion in class much more enlightening than the reading, and as such, I give this reading a 2/10.