Differences

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

--- courses:cs211:winter2011:journals:chen:chapter_1 [2011/01/16 22:34] – 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
@@ Line 22: / Line 22: @@
 ====== 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/Interesting: 5 5