Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:section1 [2012/01/14 21:56] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:section1 [2012/01/14 22:29] (current) – mugabej
@@ Line 45: / Line 45: @@
   * All executions of the G-S algorithm yield the same matching. Each man ends up with the best possible partner as long as all men prefer different women.
       * A woman //w// is a //valid partner// of man //m// if there is a stable matching that contains the pair (//m,w//).
-      * //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//
+      * //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)//  denotes the // best valid partner//  of // 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*.
+      * For a woman // w// , // m//  is a // valid partner//  if there is a stable matching that contains the pair (// m,w// ). // m//  is the // worst valid partner//  of // w// if // m//  is a valid partner of // w//  and no man whom // w//  ranks lower than // m//  is a valid partner of hers.
+      * 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,it's hard to have a stable matching.Also, when the size of the individuals increases( if we go back to the applicants and companies/colleges), the problem increases its complexity and the solution becomes harder to find. So the question I have is: To what extent can this solution be extended to solve the more complex problem involving applicants/companies?\\
+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.