Differences

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

--- courses:cs211:winter2018:journals:holmesr:section_1.1 [2018/01/16 21:26] – 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 7: / Line 9: @@
 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. This is a considerable improvement over a brute force approach which would run in O(n!) time.
+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.