Differences

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

--- courses:cs211:winter2018:journals:holmesr:section_1.1 [2018/01/16 18:19] – holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_1.1 [2018/01/21 17:37] (current) – holmesr
@@ Line 1: / Line 1: @@
-====== Section 1.1 ======
+====== Chapter 1 ======
+===== Section 1.1 =====
 Section 1.1 deals with the Stable Matching Problem. The algorithm that solves this problem can be used for a variety of different applications, including matching residents with hospitals, job candidates with jobs, or freshman girls with sororities. We will talk about it in terms of matching men and women in monogamous, heteronormative relationships.
@@ Line 5: / Line 7: @@
 First, we must define a stable matching as 1) all matches are perfect (monogamous) and 2) no matches are unstable. It is necessary to note here that an unstable match is one where //m// prefers //w// to his current match and //w// prefers //m// to her current match. So in order to devise a method to match each man and women in a stable way, we need a set of men of size n, a set of women of size n and a preference list for each man and woman.
-The algorithm works by choosing a man //m// and looping through the women in his preference list from top to bottom. If a woman is not engaged or is engaged to a man //m'// who ranks lower on her preference list than //m//, then she will accept //m//'s proposal. If she is engaged to a man //m''// that ranks higher on her preference list than //m//, she will turn down //m//. In this way, men's matches can only get worse throughout the running of the algorithm while
+The algorithm works by choosing a man //m// and looping through the women in his preference list from top to bottom. If a woman is not engaged or is engaged to a man //m'// who ranks lower on her preference list than //m//, then she will accept //m//'s proposal. If she is engaged to a man //m''// that ranks higher on her preference list than //m//, she will turn down //m//. In this way, men's matches can only get worse throughout the running of the algorithm while women's matches only get better.
+Finally, this algorithm runs in O(n<sup>2</sup>) time, since at the worst case it will go all the way through each of the n men's preference lists of size n before it finds a stable matching.