Differences

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

--- courses:cs211:winter2011:journals:david:chapter1 [2011/01/19 00:25] – [1.1 - A First Problem: Stable Matching] margoliesd
+++ courses:cs211:winter2011:journals:david:chapter1 [2011/01/19 00:59] (current) – [1.2 - Five Representative Problems] margoliesd
@@ Line 12: / Line 12: @@
 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.