Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:chen:chapter_1 [2011/01/13 16:51] – zhongc | courses:cs211:winter2011:journals:chen:chapter_1 [2011/01/19 04:46] (current) – [1.2: 5 Representative Problems] zhongc | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Chapter 1 ====== | + | ======= Chapter 1 ======= |
My notes on Chapter 1 readings | My notes on Chapter 1 readings | ||
- | ===== 1.1: Stable Matching ===== | + | ====== 1.1: Stable Matching |
+ | ===== Brief Summary ===== | ||
+ | This sections talks about the origination of the matching problem and the real-life implications such problem can have. A stable, self-enforcing matching system has to be established in order to have everyone’s self-interest prevent offers from being retracted or redirected. The section then shows an algorithm that produces stable matching and shows a proof of the effectiveness of the algorithm. | ||
- | ===== 1.2: 5 Representative Problems | + | ===== Motivation |
+ | The motivation stems from the demand to avoid chaos in any matching problem such as application process of a summer internships, | ||
- | Summarize | + | ===== Question ===== |
+ | How useful is this algorithm in real life? This algorithm assumes | ||
+ | ===== Readable/ | ||
+ | Readable: 5 | ||
+ | Interesting: | ||
+ | |||
+ | |||
+ | ====== 1.2: 5 Representative Problems ====== | ||
+ | |||
+ | **Interval sheduling** | ||
+ | Input: Jobs with periods. | ||
+ | Output: Maximum subset of compatible jobs. | ||
+ | |||
+ | **Weighted Interval sheduling** | ||
+ | Input: Jobs with periods and weights. | ||
+ | Output: Maximum weighted subset of compatible jobs. | ||
+ | |||
+ | **Bipartite matching** | ||
+ | Matchings in bipartite graphs can model situations in which objects are | ||
+ | being assigned to other objects. | ||
+ | output: maximum matching | ||
+ | |||
+ | **Independant set** | ||
+ | Motivation: 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. | ||
+ | Interval Scheduling and Bipartite Matching can both be encoded as special | ||
+ | cases of the Independent Set Problem. | ||
+ | |||
+ | |||
+ | Readable/ |