Differences

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

--- courses:cs211:winter2018:journals:boyese:chapter1 [2018/01/11 23:08] – boyese
+++ courses:cs211:winter2018:journals:boyese:chapter1 [2018/01/22 21:56] (current) – [Section 1.1 : A First Problem: Stable Matching] boyese
@@ Line 1: / Line 1: @@
-===Section 1.1 : A First Problem: Stable Matching===
+====== Chapter 1 ======
+=====Section 1.1 : A First Problem: Stable Matching=====
 The stable matching problem/algorithm attempts to find a stable matching (pairing) between individuals of two sets of the same size given a ranking of preferences for each individual within the set. A matching is a mapping from the elements of one set to the elements of the other set.\\
@@ Line 14: / Line 16: @@
 There are several truths regarding the stable marriage problem that can all be verified by proof by contradiction.\\
 Note that w represents a woman and m represents a man.\\
-.1  w remains engaged from the point at which she receives her first proposal; and the sequence of partners to which she is engaged gets better and better.\\
+.1  w remains engaged from the point at which she receives her first proposal; and the sequence of partners to which she is engaged gets better and better.
-.2  The sequence of women to whom m proposes gets worse and worse.\\
+.2  The sequence of women to whom m proposes gets worse and worse.
-.3  The G-S (Gale-Shapley) algorithm terminates after at most n<sup>2</sup> iterations of the While loop.\\
+.3  The G-S (Gale-Shapley) algorithm terminates after at most n<sup>2</sup> iterations of the While loop.
-.4  If m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.\\
+.4  If m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.
-.5  The set S returned at termination is a perfect matching.\\
+.5  The set S returned at termination is a perfect matching.
-.6  Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.\\
+.6  Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.
 A sketch of the Gale-Shapley algorithm follows: \\