Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:ahmadh:ch1 [2018/01/16 22:56] – ahmadh | courses:cs211:winter2018:journals:ahmadh:ch1 [2018/01/17 00:21] (current) – ahmadh | ||
|---|---|---|---|
| Line 5: | Line 5: | ||
| The problem stems from the question that could one design a college admissions process, or a job recruiting process, that was self-enforcing, | The problem stems from the question that could one design a college admissions process, or a job recruiting process, that was self-enforcing, | ||
| - | This problem can be reduced to a simple problem, the solution to which can be extended to solve the Stable Matching Problem in general: given a set of n men and n women and an order of preference for each man and woman, find a stable matching such that everyone ends up married to somebody and nobody is married to more than one person. A sketch of the Gale-Shapley algorithm to this problem is given below: | + | This problem can be reduced to a simple problem, the solution to which can be extended to solve the Stable Matching Problem in general: given a set of n men and n women and an order of preference for each man and woman, find a stable matching such that everyone ends up married to somebody and nobody is married to more than one person. |
| + | |||
| + | ==== Section 1.1.1: Pseudo-code for the Gale-Shapley Algorithm ==== | ||
| + | |||
| + | A sketch of the Gale-Shapley algorithm | ||
| Initially all m and w are free | Initially all m and w are free | ||
| Line 24: | Line 28: | ||
| Return the set S of engaged pairs | Return the set S of engaged pairs | ||
| - | The algorithm terminates after N^2 steps at most, since every man can at most propose to each of n women. Therefore, it is O(N^2). The proof for the algorithm is given on Page 7 of the textbook. | + | ==== Section 1.1.2: Analysis the Gale-Shapley Algorithm ==== |
| + | |||
| + | The algorithm terminates after n^2 steps at most, since every man can at most propose to each of n women. Therefore, it is O(n^2). The proof for the algorithm is given on Page 7 of the textbook. | ||
