Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:chen:chapter_1 [2011/01/16 22:33] – [Chapter 1] 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
-====== 1.1 Stable Matching Problem ======
+====== 1.1: Stable Matching Problem ======
@@ Line 18: / Line 18: @@
 Readable: 5
 Interesting: 7
-===== 1.1: Stable Matching =====
+====== 1.2: 5 Representative Problems ======
-===== 1.2: 5 Representative Problems =====
+**Interval sheduling**
+Input: Jobs with periods.
+Output: Maximum subset of compatible jobs.
-Summarize the section, issues, what you figured out, readability, ...
+**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/Interesting: 5 5