Differences

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

--- courses:cs211:winter2018:journals:ahmadh:ch1 [2018/01/16 22:01] – added content for Ch1.1 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, i.e. self-interest would prevent offers from being retracted and redirected, and all the offers would be stable?
-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. This problem is solved--efficiently--by the Gale-Shapley algorithm.
+==== Section 1.1.1: Pseudo-code for the Gale-Shapley Algorithm ====
+A sketch of the Gale-Shapley algorithm (from Page 6 of the textbook) to this problem is given below:
 	Initially all m and w are free
@@ Line 24: / Line 28: @@
 	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).
+==== 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.