Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2018:journals:melkersonr:chapter1 [2018/01/30 02:16] – melkersonr | courses:cs211:winter2018:journals:melkersonr:chapter1 [2018/01/30 02:43] (current) – melkersonr |
|---|
| * **My Questions:** Not a question, but rather a thought: I had already anticipated that the outcome would be reversed if women were the ones proposing. You'd simply be switching the places of men and women. I do have a question about analysis, though. The book says: "Thus, we find that our simple example above, in which the men’s preferences clashed with the women’s, hinted at a very general phenomenon: for any input, the side that does the proposing in the G-S algorithm ends up with the best possible stable matching (from their perspective), while the side that does not do the proposing correspondingly ends up with the worst possible stable matching” (p12). Isn't this the reverse of what we said in class and what was said on page 7, that women get better men as time goes on and men get worse women as time goes on? | * **My Questions:** Not a question, but rather a thought: I had already anticipated that the outcome would be reversed if women were the ones proposing. You'd simply be switching the places of men and women. I do have a question about analysis, though. The book says: "Thus, we find that our simple example above, in which the men’s preferences clashed with the women’s, hinted at a very general phenomenon: for any input, the side that does the proposing in the G-S algorithm ends up with the best possible stable matching (from their perspective), while the side that does not do the proposing correspondingly ends up with the worst possible stable matching” (p12). Isn't this the reverse of what we said in class and what was said on page 7, that women get better men as time goes on and men get worse women as time goes on? |
| * **Second Time Around:** I definitely think the proofs in the analysis section make more sense the second (or third) time around. I'm not the best at proofs - I usually understand the intuition, but I often don't know when you've said enough to conclude that you've proven something. Hence, I liked that the proofs were spelled out so I could follow the logic that yields a //valid// proof. In particular, the proof about stability made more sense after reading because the book says the instability would involve //two// pairs, whereas in lecture we framed it as one pair. I was confused about the question in class, and it now makes more sense. | * **Second Time Around:** I definitely think the proofs in the analysis section make more sense the second (or third) time around. I'm not the best at proofs - I usually understand the intuition, but I often don't know when you've said enough to conclude that you've proven something. Hence, I liked that the proofs were spelled out so I could follow the logic that yields a //valid// proof. In particular, the proof about stability made more sense after reading because the book says the instability would involve //two// pairs, whereas in lecture we framed it as one pair. I was confused about the question in class, and it now makes more sense. |
| * **Note To Self:** I want to remember that “A useful strategy for upper-bounding the running time of an algorithm…is to find a measure of progress. Namely, we seek some precise way of saying that each step taken by the algorithm brings it closer to termination” (p7). I already knew this, but I like the way that it's phrased here. | * **Note to Self:** I want to remember that “A useful strategy for upper-bounding the running time of an algorithm…is to find a measure of progress. Namely, we seek some precise way of saying that each step taken by the algorithm brings it closer to termination” (p7). I already knew this, but I like the way that it's phrased here. |
| * **Readability:** I think everything leading up to the subsection about extensions should get an 8 or 9 in readability. It's fairly straightforward and most of the algorithm was addressed in layman's terms rather than as complicated math. The extensions subsection, though, had a good bit of math notation and that's sometimes hard to read for understanding if you're not a math major (or maybe even if you are). I do appreciate, though, that the authors level with the reader and acknowledge when things aren't obvious. For example, after proposition 1.7, that every execution of the G-S algorithm results in the set of pairs where each man is matched with his "best possible partner," they say "why couldn't it happen that two men have the same best valid partner?" (p10). | * **Readability:** I think everything leading up to the subsection about extensions should get an 8 or 9 in readability. It's fairly straightforward and most of the algorithm was addressed in layman's terms rather than as complicated math. The extensions subsection, though, had a good bit of math notation and that's sometimes hard to read for understanding if you're not a math major (or maybe even if you are). I do appreciate, though, that the authors level with the reader and acknowledge when things aren't obvious. For example, after proposition 1.7, that every execution of the G-S algorithm results in the set of pairs where each man is matched with his "best possible partner," they say "why couldn't it happen that two men have the same best valid partner?" (p10). |
