Differences

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

--- courses:cs211:winter2018:journals:bairdc:chapter1 [2018/01/16 06:13] – [1.1 – A First Problem: Stable Matching] bairdc
+++ courses:cs211:winter2018:journals:bairdc:chapter1 [2018/01/16 06:19] (current) – [1.1 – A First Problem: Stable Matching] bairdc
@@ Line 9: / Line 9: @@
 Basic Sketch of the Gale-Shapley algorithm for stable matching:
+<code>
 while some man is free and hasn't proposed to every woman
- Choose such a man m
+    Choose such a man m
- w = 1st woman on m's list to whom m has not yet proposed
+    w = 1st woman on m's list to whom m has not yet proposed
- if w is free
+    if w is free
-    assign m and w to be engaged
+       assign m and w to be engaged
- else if w prefers m to her fiancé m'
+    else if w prefers m to her fiancé m'
-    assign m and w to be engaged and m' to be free
+       assign m and w to be engaged and m' to be free
- else
+    else
-    w rejects m
+       w rejects m
+</code>
 After reading the section, all the proofs make much more sense now. The only one that still is a little confusing to me is (1.8) that each woman in a stable matching is paired with her worst valid partner. It makes some sense, but I have to read over it a few times to make it make sense in my head. I'm sure it will make more sense over time. This section is a 8/10 in terms of readability and being interesting to me.