Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:jeanpaul:section1 [2012/01/14 22:00] – mugabej | courses:cs211:winter2012:journals:jeanpaul:section1 [2012/01/14 22:29] (current) – mugabej | ||
|---|---|---|---|
| Line 47: | Line 47: | ||
| * //w// is the // best valid partner // of // m// if // w// is a // valid partner// of // m// and no woman whom // m// ranks higher than // w// is his // valid partner// . The notation // best(m)// | * //w// is the // best valid partner // of // m// if // w// is a // valid partner// of // m// and no woman whom // m// ranks higher than // w// is his // valid partner// . The notation // best(m)// | ||
| * If we let S* denote the set of pairs {(// m,best(m)// ):// m// in M}, every execution of the G-S algorithm results in the set S*. | * If we let S* denote the set of pairs {(// m,best(m)// ):// m// in M}, every execution of the G-S algorithm results in the set S*. | ||
| + | * For a woman // w// , // m// is a // valid partner// | ||
| + | * In the stable matching S*, each woman is paired with her // worst valid partner// . | ||
| + | \\ | ||
| + | \\ | ||
| + | After re-reading this section, I still think that it is very hard to implement an algorithm that may satisfy both those who propose and those who are proposed to. In practice, | ||
| + | After re-reading this section, I appreciated even more the way the approach of this problem was made: from a clearly complex problem, devise a simpler version of the problem whose solution may extend to the more complex problem. It's a very admirable process that is really useful in solving most of the problems.\\ | ||
| + | |||
| + | The reading was interesting but I had trouble progressing at times. I give this section a 7 out of 10. | ||
| + | |||
| + | |||
