A Further Enhancement of Gale - Shapley Algorithm Applied to course preference incoming PLM Freshmen Students / Rodel B. Bernarbe; Knedrich Karl B. Luna and Edrianne T. Reyes. 6

Undergraduate Thesis (BS Computer Science) - Pamantasan ng Lungsod ng Maynila, 2012. 56

5

ABSTRACT: The Gale-Shapley algorithm involves a number of rounds (or iterations) where each unengaged man proposes to the most-preferred woman to whom he has not yet proposed.Each woman then considers all her suitors and tells the one she most prefers Maybe and all the rest of them No.She is then provisionally engaged to the suitor she most prefers so far, and the suitor is likewise provisionally engaged to her. In the first round, a) each unengaged man proposes to the woman he prefers most, and then b) each woman replies maybe to her suitor she most prefers and no to all other suitors. In each subsequent round, first a) each unengaged man proposes to the most-preferred woman to whom he has not yet proposed (regardless of whether the woman is already engaged), and then b) each woman replies maybe to her suitor she most prefers (whether her existing provisional partner or someone else) and rejects the rest (again perhaps including her current provisional partner). The provisional nature of engagements preserves the right of an already-engaged woman to trade up (and, in the process, to jilt her until-then partner). The algorithm is applied to different stable matching problems like matching students to their preferred course. Students are matched according to their given course choices and the required average grade in the courses.

5