====== Chapter 1 ======

===== 1.1: Stable Matching Problem  =====


I read the chapter before we worked on this problem in class and it made everything so simple and easy to understand. I am also in the middle of sorority recruitment and so it seemed very relevant. Since as a member of a sorority we have preferences and the freshman have preferences and this whole week is based on matching the sorority with a pledge class. What is actually really interesting about recruitment that most people don't know is that a computer algorithm is used to do the matching every night. (Pretty crazy). 

The text goes over an example with marriages, which we also used in class. The Gale-Sharpley algorithm to solve it is very simple and seeing it in code made it clear why it worked so well. I was surprised to find that it had a unique stable solution and that the women and men experience the opposite preference changes through out the algorithm. Women move to better matches, while men move to worse. 

I found the proofs most interesting because they were succint and simple. I am also a sucker for a proof by contradiction. I think the best proof was showing it was a stable matching since once you know the trick to show the contradiction it is only a couple lines.  I would like to go over the proof that the solution is unique in class since that is the most complicated. 

===== 1.2 Five Representative Problems =====
 
The text briefly went through the following five problems. I pulled a few notes just to remember what they are. 
  * Interval Schedulings
      * Resource with over lapping time requests
      * Goal is to maximize number of requests accepted
  * Weighted interval scheduling
      * Similar to the above problem but changed the goal. 
      * Instead  interval is associated with a value maximize the interval values 
  * Bipartite Matching
      * matching is a set of ordered pairs
      * perfect matching is when no overlapping between pairs
      * create a bipartite graph with nodes
      * similar to stable matching problem, but no weights. 
      * max number of matchings
      * perfect matching if # of x nodes = number of y nodes and max matching = n 
  * Independent Set
      * general problem 
      * want to find largest goup you can invite with out offending any one
      * no efficient algorithm exists
  * Competitive Facility Location
      * about who wil win when competing for locations, (nodes)
      * A little confused by this one.