Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2012:journals:carrie:ch1 [2012/01/10 15:53] – created hopkinsc | courses:cs211:winter2012:journals:carrie:ch1 [2012/01/19 19:38] (current) – hopkinsc | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | 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. | ||
| + | |||
| + | ===== 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 | ||
| + | * 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. | ||
