This is an old revision of the document!

• Brief summary of the section
  • ~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
• “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
• “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