Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:boyese:chapter1 [2018/01/22 21:55] – [Section 1.1 : A First Problem: Stable Matching] boyese | courses:cs211:winter2018:journals:boyese:chapter1 [2018/01/22 21:56] (current) – [Section 1.1 : A First Problem: Stable Matching] boyese | ||
|---|---|---|---|
| Line 16: | Line 16: | ||
| There are several truths regarding the stable marriage problem that can all be verified by proof by contradiction.\\ | 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.\\ | Note that w represents a woman and m represents a man.\\ | ||
| - | + | ||
| - | 1.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.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.2 The sequence of women to whom m proposes gets worse and worse.\\ | + | 1.2 The sequence of women to whom m proposes gets worse and worse. |
| - | 1.3 The G-S (Gale-Shapley) algorithm terminates after at most n< | + | 1.3 The G-S (Gale-Shapley) algorithm terminates after at most n< |
| - | 1.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.\\ | + | 1.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. |
| - | 1.5 The set S returned at termination is a perfect matching.\\ | + | 1.5 The set S returned at termination is a perfect matching. |
| - | 1.6 Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.\\ | + | 1.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: \\ | A sketch of the Gale-Shapley algorithm follows: \\ | ||
