Differences

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

--- courses:cs211:winter2018:journals:hornsbym:chapter_1 [2018/01/16 01:34] – hornsbym
+++ courses:cs211:winter2018:journals:hornsbym:chapter_1 [2018/01/16 01:40] (current) – hornsbym
@@ Line 1: / Line 1: @@
 ====== Chapter 1 ======
-<Enter overview of chapter 1 here>
+This chapter deals with the Stable Matching Problem. In Chapter 1.1, the authors sketch out the algorithm and prove the following:\\
+(A) The Gale-Shapely algorithm terminates after n<sup>2</sup> iterations\\
+(B) The final matching is a perfect matching\\
+(C) The final matching is stable
 ===== Section 1.1(The Stable Matching Problem) =====
-This section deals with the Stable Matching Problem, which was first posed by David Gale and Lloyd Shapely in 1962. This algorithm seeks to assign job applicants to potential employers in a way such that:\\
+This section deals with the Stable Matching Problem, which was first posed by David Gale and Lloyd Shapely in 1962. This algorithm seeks to assign job applicants to potential employers in a way such that:
     "(i) Employers prefer every one of its accepted applicants to the remaining applicants; or
      (ii)Accepted job applicants prefer their current situation over working for other potential employers."
@@ Line 10: / Line 13: @@
 \\
 The algorithm follows the following steps:
-\\
      (1)Each man proposes to each woman in order of his preference, until a woman accepts.
      (2)Each woman accepts any proposal if she's free. If she's already engaged, she will only accept the proposal if she prefers the new man.