| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:melkersonr:chapter1 [2018/01/16 01:15] – melkersonr | courses:cs211:winter2018:journals:melkersonr:chapter1 [2018/01/30 02:43] (current) – melkersonr |
|---|
| * Brief summary of the section | ====== Chapter 1 - Introduction: Some Representative Problems ====== |
| * ~1 paragraph of about 5-10 sentences per section | |
| * feel free to write more if that will help you | |
| * Include motivations for the given problem, as appropriate | |
| * Questions you have about motivation/solution/proofs/analysis | |
| * Discuss anything that makes more sense after reading it again, after it was presented in class (or vice versa) | |
| * Anything that you want to remember, anything that will help you | |
| * Say something about how readable/interesting the section was on scale of 1 to 10 | |
| |
| * “To get at the essence of this concept, it helps to make the problem as clean as possible” p3 | ===== Section 1.1 ===== |
| * “This is an important point to remember as we go forward – it’s possible for an instance to have more than one stable matching” p 5 | Note: I accidentally read this section //before// class, rather than after. My "second time around" response should still be interpreted as after class, though, because I reread the section after class in order to write this Wiki. All Wiki's following this one, though, should be based on reading that I did strictly after the material was first presented in class. |
| * “PROOF: 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.” p 7 | |
| * Proposition 1.4 and its following proof required multiple reads. It’s not obvious that the returned set is a perfect matching. | |
| * Pg 9: I had already anticipated that the outcome would be reversed if women were the ones proposing | |
| * “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.” P 12 | |
| * 5 representative problems: | |
| * interval scheduling | |
| * “When a greedy algorithm can be shown to find an optimal solution for all instance of a problem, it’s often fairly surprising. We typically learn something about the structure of the underlying problem from the fact that such a simple approach can be optimal” p 14 | |
| * weighted interval scheduling | |
| * bipartite matching | |
| * had to read this twice, because was confused upon looking back at Figure 1.3 like the text suggests | |
| * yes, I saw the perfect matching in Figure 1.5 | |
| * “There is, however, a very elegant and efficient algorithm to find a maximum matching; it inductively builds up larger and larger matchings, selectively backtracking along the way. This process is called augmentation, and it forms the central component in a large class of efficiently solvable problems called network flow problems” p 16 | |
| * interdependent set | |
| * “the independent set problem encodes any situation in which you are trying to choose from among a collection of objects and there are pairwise conflicts among some of the objects” p16 | |
| * transforming bipartite matching to a special case of independent set is confusing | |
| * last paragraph about independent sets recalls 313. How does one know that a problem is NP-complete? Like, what if you categorize something that’s not NP-complete as NP-complete, solve it, then erroneously conclude that everything else in NP-complete has a solution? | |
| * competitive facility location | |
| * didn’t hear about PSPACE-complete problems in 313 | |
| * “The notion of PSPACE-completeness turns out to capture a large collection of problems involving game-playing and planning; many of these are fundamental issues in the area of artificial intelligence” p18 | |
| |
| | * **Summary:** Section 1.1 is A First Problem: Stable Matching. The section begins by describing the problem's origins, citing David Gale and Lloyd Shapley as partial sources. The authors quickly shift to presenting the problem in a way that the readers, presumably college students, should understand: CS juniors applying for summer internships. After the example, the authors reveal that 10 years before Gale and Shapley the National Resident Matching Program was using a similar approach to match residents to hospitals, which helps the authors to establish the significance of the Stable Matching Problem. After this introduction to the problem, the authors move on to simplifying the problem, claiming that the streamlined version can be extended to the general case. Since the streamlined version has a 1:1 relationship, the authors now frame it as men and women getting married. From here, the text starts to establish specifics about the algorithm for the Stable Matching Problem and finally touches on analyzing and extending the algorithm. |
| | * **Motivations:** This section's given problem is the Stable Matching Problem. This problem was motivated ("in part") by David Gale and Lloyd Shapley asking if the process by which students are admitted to college, job applicants are offered the positions, etc can be self-enforcing. Their definition of self-enforcing is that entities cannot act "in their self-interest" (p2). They wanted to see if there was a way to design this matching system such that the matches are stable: "there are no further outside deals that can be made" (p2). |
| | * **About the Algorithm:** In brief, the algorithm to solve the Stable Matching Problem goes as follows. The people are all initially single, and the men propose to the women. While there are any men free and there are women to whom he has not yet proposed, he proposes to the women highest on his preferences to whom he has not yet proposed. If the woman is single, they become engaged. If the woman is already engaged but she prefers this man to her fiancé, she dumps her fiancé and becomes engaged to this new man. If the woman is already engaged and does not prefer this new man, she stays with her fiancé and the man in question remains single. The algorithm terminates with a perfect, stable matching (which the authors prove in the analysis section). The intuitions associated with this algorithm are that once a woman becomes engaged, she stays engaged; a man may go back and forth between engaged and single; for any man, his woman's ranking can only go down; and for any woman, her man's ranking can only go up. The runtime of the algorithm is O(n^2), where n is the number of men (or women), because n^2 is the maximum number of proposals that can occur. |
| | * **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. |
| | * **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). |
