Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2014:journals:stephen:home:chapter-1.1 [2014/01/14 01:26] – created rowleys | courses:cs211:winter2014:journals:stephen:home:chapter-1.1 [2014/01/14 01:28] (current) – rowleys | ||
|---|---|---|---|
| Line 4: | Line 4: | ||
| It is implemented as follows: | It is implemented as follows: | ||
| - | Initially all m that are elements of M and w that are elements of W are free. | + | |
| - | While there is a man m who is free and hasn't proposed to every woman | + | While there is a man m who is free and hasn't proposed to every woman |
| - | Choose such a man m | + | Choose such a man m |
| - | Let w be the highest ranked woman in m's preference list to whom m has not yet proposed | + | Let w be the highest ranked woman in m's preference list to whom m has not yet proposed |
| - | If w is free then | + | If w is free then |
| - | (m, w) become engaged | + | |
| - | Else w is currently engaged to m(prime) | + | |
| - | If w prefers m(prime) to m then | + | |
| - | m remains free | + | |
| - | Else w prefers m to m(prime) | + | |
| (m, w) become engaged | (m, w) become engaged | ||
| - | | + | Else w is currently engaged to m(prime) |
| - | return the set S of engaged pairs | + | If w prefers m(prime) to m then |
| + | m remains free | ||
| + | Else w prefers m to m(prime) | ||
| + | (m, w) become engaged | ||
| + | | ||
| + | return the set S of engaged pairs | ||
| This runtime in worst case is O(n^2), because the while loop runs through both all men and all those men's preferences - n * n. | This runtime in worst case is O(n^2), because the while loop runs through both all men and all those men's preferences - n * n. | ||
