Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:shannon:section1 [2014/01/15 01:16] – nollets | courses:cs211:winter2014:journals:shannon:section1 [2014/01/15 01:16] (current) – nollets | ||
|---|---|---|---|
| Line 16: | Line 16: | ||
| If w prefers m’ to m then m remains free | If w prefers m’ to m then m remains free | ||
| Else w prefers m to m’ and (m,w) becomes engaged and m’ becomes free | Else w prefers m to m’ and (m,w) becomes engaged and m’ becomes free | ||
| - | | + | |
| The runtime of the algorithm is n2 as the loop will execute at most n2 and the operations within the loop run in constant time. The way the while loop is worded ensures that the algorithm will not terminate until all men and women are matched. In this algorithm a woman’s partner can only “upgrade” while a man can only “downgrade” his partner. | The runtime of the algorithm is n2 as the loop will execute at most n2 and the operations within the loop run in constant time. The way the while loop is worded ensures that the algorithm will not terminate until all men and women are matched. In this algorithm a woman’s partner can only “upgrade” while a man can only “downgrade” his partner. | ||
| The unfairness idea made more sense after reading it. We briefly discussed it in class but the book elaborated upon the subject. | The unfairness idea made more sense after reading it. We briefly discussed it in class but the book elaborated upon the subject. | ||
| I find this problem to be very interesting so the section was a 9. I like the idea that matching people, even based off of their own emotions and preferences can be boiled down to an algorithm. | I find this problem to be very interesting so the section was a 9. I like the idea that matching people, even based off of their own emotions and preferences can be boiled down to an algorithm. | ||
