Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| 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 ====== | ====== Chapter 1 ====== | ||
| - | <Enter overview of chapter 1 here> | + | This chapter |
| + | (A) The Gale-Shapely algorithm terminates after n< | ||
| + | (B) The final matching is a perfect matching\\ | ||
| + | (C) The final matching is stable | ||
| ===== Section 1.1(The Stable Matching Problem) ===== | ===== 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: | ||
