Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2018:journals:cohene:home:chapter1 [2018/01/15 19:23] – created cohene | courses:cs211:winter2018:journals:cohene:home:chapter1 [2018/01/28 21:49] (current) – cohene | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Chapter 1 ====== | ====== Chapter 1 ====== | ||
| - | ===== 1.1- Stable Matching Problem ===== | + | ===== 1.1: Stable Matching Problem ===== |
| + | |||
| + | Chapter one was very easy to read, as it reinforced up what we had learned in class. In chapter 1.1, the authors discussed the Stable Matching Problem, which has many applications beyond those discussed in the textbook. When learning about the process behind the Stable Matching Problem in class, it made a lot of sense. Reading it in the textbook helped to reinforce my understanding. | ||
| + | |||
| + | The Stable Matching Problem originated in 1962 when David Gale and Lloyd Shapely asked if one could design a self-enforcing college admissions process. The Gale-Shapely algorithm in this instance was applied to matching men and women based on their preferences. In a set M = (m1, m2, ... , mn) of n men and set W = (w1, w2, ... , wn) of n women, M x W denotes the set of all possible ordered pairs of the form (m, w). A match is denoted by S, a set of ordered pairs where each member of M and W are in at most one pair of S, and a perfect matching S' is a set where each member of M and W appears in exactly a single pair in S'. | ||
| + | |||
| + | While I question the use of the example involving matching preferences between men and women, it does nicely demonstrate the algorithm. Essentially, | ||
