Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2012:journals:carrie:ch1 [2012/01/11 18:39] – 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 | ||
| - | 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). | 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). | ||
| Line 8: | Line 10: | ||
| 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 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 | + | ===== 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 | * Interval Schedulings | ||
| + | * Resource with over lapping time requests | ||
| + | * Goal is to maximize number of requests accepted | ||
| * Weighted interval scheduling | * Weighted interval scheduling | ||
| + | * Similar to the above problem but changed the goal. | ||
| + | * Instead | ||
| * Bipartite Matching | * 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 | * Independent Set | ||
| + | * general problem | ||
| + | * want to find largest goup you can invite with out offending any one | ||
| + | * no efficient algorithm exists | ||
| * Competitive Facility Location | * Competitive Facility Location | ||
| + | * about who wil win when competing for locations, (nodes) | ||
| + | * A little confused by this one. | ||
| + | |||
