Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:shannon:section1 [2014/01/15 01:14] – nollets | courses:cs211:winter2014:journals:shannon:section1 [2014/01/15 01:16] (current) – nollets | ||
|---|---|---|---|
| Line 4: | Line 4: | ||
| The section then walked through how to build the algorithm step by step and proved that the algorithm actually solved our problem. It showed that the algorithm terminated, created perfect matches (one man to one woman and no one left out), and stable matches. | The section then walked through how to build the algorithm step by step and proved that the algorithm actually solved our problem. It showed that the algorithm terminated, created perfect matches (one man to one woman and no one left out), and stable matches. | ||
| Finally, the section looked deeper into questions one could ask about the algorithm. It discussed fairness, as in the algorithm the man is allowed to choose his first choice of woman, so often men can get their first choice while women do not. More generalized, | Finally, the section looked deeper into questions one could ask about the algorithm. It discussed fairness, as in the algorithm the man is allowed to choose his first choice of woman, so often men can get their first choice while women do not. More generalized, | ||
| + | |||
| This problem was motivated by the need to create a system that could provide matchings that made people and companies happy while at the same time preventing self-interest from interfering. | This problem was motivated by the need to create a system that could provide matchings that made people and companies happy while at the same time preventing self-interest from interfering. | ||
| + | |||
| The algorithm is outlined like this: | The algorithm is outlined like this: | ||
| Initially all men and women are free/ | Initially all men and women are free/ | ||
| Line 14: | 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 | ||
| - | Return set of engaged pairs. | + | |
| 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. | ||
