Differences

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

--- courses:cs211:winter2018:journals:cantrella:chapter_1 [2018/01/15 22:26] – cantrella
+++ courses:cs211:winter2018:journals:cantrella:chapter_1 [2018/01/15 22:46] (current) – [Section 1.1] cantrella
@@ Line 1: / Line 1: @@
 ====== Chapter 1 ======
-This is chapter 1, I wish I knew how to increase text size :(
+===== Section 1.1 =====
+The algorithm presented in section 1.1 is a solution to the stable matching problem. The algorithm assumes there are two sets of people, one of //n// men and one of //n// women. Each man in the set ranks each woman from 1 to n while the women do the same for the men. Using the sets of men and women and each person's preferences, the algorithm generates a set of pairs that match each man to each woman according to their preferences.
+At a high level, the algorithm iterates through the list of men and matches him with his highest preferred women. If the women the man chooses is single, then the two are paired up. If, however, the woman is already matched with another man, the woman looks at her preference list and chooses to pair with whichever man is higher on the list. Once every man is matched with a woman than the algorithm terminates.
+The worst-case runtime of this algorithm is O(N^2). This is because the while loop which contains the algorithm has the built-in condition that while there is some man //m// who is free and has not proposed to every woman, the loop will continue to run. In the worst case, each man will propose to every woman, causing the loop to run //n^2// number of times.
+After going over this algorithm in class, there were a few things that became apparent to me. First off, once a man is matched with a woman, his final pairing can only go down from there. Conversely, once a woman became matched, her final pairing could only go up. This is because of how the algorithm works by default, with men proposing to women and women turning down possible suitors and pairing up with more preferred ones. If the order of the algorithm were reversed i.e., women proposed to men, then the direction of suitor preference for men and women would switch.
+This particular section was interesting but I found some of the notation confusing. There were certain statements that took me longer than I would have liked to decipher. In addition, I found that some of the assumptions used when arguing the later proofs were introduced quickly and without warning. This caused even further confusion for me as I had to go back to find where the assumptions were in the text. Overall, I would give this section a rating of a 6.