Differences

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

--- courses:cs211:winter2011:journals:david:chapter1 [2011/01/18 02:16] – created margoliesd
+++ courses:cs211:winter2011:journals:david:chapter1 [2011/01/19 00:59] (current) – [1.2 - Five Representative Problems] margoliesd
@@ Line 1: / Line 1: @@
 =====Chapter 1 - Introduction: Some Representative Problems=====
 ====1.1 - A First Problem: Stable Matching====
+The stable matching problem deals with creating a self-reinforcing selection process. There are two groups, and all the members of each group has a preference profile that lists ranks all members of the other group in order of who that member would like to be matched with. The solution should be self-reinforcing, meaning that members not paired together have no desire to change their matching after the algorithm finishes. The Gale-Shapley algorithm solves the problem as follows for two groups A and B, where all members are initially unmatched:
+<code>While there is still a free member in A
+Choose a member "a" in A
+Let "b" be highest ranked member of B in "a"'s preference list that a has not already tried to match with
+If "b" is not already matched with another member of A, then "b" matches with "a"
+Else if "b" is already matched
+     If "a" is higher on "b"'s preference list than "b"'s current match, then a matches with "b" and "b"'s previous match becomes unmatched
+     Else "a" remains free</code>
+In terms of readability I would rank this section a 7/10.
+====1.2 - Five Representative Problems====
+We have to be mathematically precise in how we define in order to write and prove an algorithm for it. Graphs can show pairs between two sets of data. The Interval Scheduling Problem attempts to maximize the number of individuals that can use a resource when each individual requests a specific time interval (a starting and stopping time, not simply a length of time). The Weighted Interval Scheduling Problem attaches weights to each individual's interval and the goal is to maximize the value of the schedule when adding up all the weights. The Bipartite Matching Problem uses a bipartite graph where two groups of nodes are arranged in separate columns and edges are drawn between compatible nodes from one group to the other. The goal of the Bipartite Matching Problem is to find the maximum number of matches. The Independent Set Problem uses a graph of nodes with edges connecting some of them. The goal is to find the largest set of nodes for which no two nodes share an edge. The Competitive Facility Location Problem has two players that compete to select nodes that have weights. Players alternate who gets to choose, but the set of all nodes must be independent. The problem asks if one player can reach a certain value (the addition of all weights) regardless of what the other player chooses.
+I give this section a 7/10 for readability.