Differences

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

--- courses:cs211:winter2014:journals:annebailey:home [2014/03/23 18:06] – dickensa
+++ courses:cs211:winter2014:journals:annebailey:home [2014/03/30 18:57] (current) – dickensa
@@ Line 112: / Line 112: @@
 We will add to our interval scheduling problem by looking at n requests which use resources between time 0 and W, and have weights w_i for problem i.  we want the sums of the weights to be as large as possible without exceeding W.  We call this a knapsack problem because we fill our knapsack with items of value v_i and weight w_i until the total weight does not succeed W and the value is the maximum problem.  We need to work out enough subproblems that we know OPT(n-1)’s value and the best possible solution on n-1 for weight W-w_n.  Then OPT(I,w) = max(OPT(i-1,w), w_i + OPT(i-1,w-w_i)).  To do that we will build a table of the values of OPT(i,w) which only computes each value once.  Finding M[i,w] comes from two other values in the table, so we compute each of these in constant time, so the running time increases in proportion with the number of entries in the table, so Subset-Sum(n,W) runs with O(nW) time, so it is pseudo-polynomial, which grows very quickly with large inputs.  Given M, we can find the optimal set with O(n) time.  Therefore, our total running time is O(nW).  I found this section very readable and helpful, but my understanding was dependent on having already studied this in class.  (6/10)
+=====6.6 Sequence Alignment =====
+We use sequence alignment to compare strings using shortest paths in graphs with any integer weight to edges.  When we compare strings we can use gaps to minimize mismatches.  To define the similarity of two strings, we should look at the indexing without gaps.  An alignment will denote which symbols are the same in order without counting the gap spaces.  For example, if the second spot of the first word and the first spot in the second word match, we add the pair (2,1) to the set of alignments.  When positions don’t match, there is a gap, and it has cost delta > 0.  Mismatches cost a specific amount, and having the same letter costs nothing.  The cost total is the sum of gap and mismatches.  The first alignment of strings will only be better if the number of gaps times delta + the sum of the mismatches is less than the number of gaps times delta; in this case the first way uses mismatched letters and the second puts in gaps everywhere to avoid mismatches.  Similarity is therefore the minimum cost of an alignment between X and Y.  If we have an optimal M, either (m,n) is in M, the mth position of X is not matched, or the nth position of Y is not matched.  The recurrence for i and j will be OPT(i,j) = min([alpha_x_i,y_j + OPT (i-1,j-1) , delta + OPT (i-1,j), delta + OPT(i,j-1)]).  If (i,j) is in our optimal M, then the first of these WILL achieve the minimum value.  This runs in time O(mn) since A has O(mn) values, and we spend at most constant time on each.  We have the minimum cost path from i to j, f(i,j) = OPT(i,j).  I thought this section was a bit confusing because it failed to give an algorithm for how exactly to choose where to put gaps.  (8/10)
+=====7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm =====
+Transportation uses a network model in which edges carry traffic and nodes let you switch between different highways; then networks will have capacities on the edges, source nodes that generate traffic, and destinations which take in and eliminate traffic.  These highways will have directions along which the traffic flows, so they will be directed graphs with capacities on edge e c_e, one source node s, and one sink node t.  We want to move the traffic around so that we efficiently use the capacities available.  The maximum flow equals the minimum capacity of an area, called the minimum cut.  To find the maximum flow, we want to push as much flow as possible along the edges from s to t.  We can push backwards and create a residual graph.  I do not understand at all how the pushing backwards of flow works.  We can show that the Ford-Fulkerson Algorithm terminates while computing an s-t flow on G after at most C, the sum of the capacities of the edges iterations on the while loop.  The bounds can simply be O(m), so O(mC).  This section confused me instead of clearing things up.  (4/10)
+=====7.2 Maximum Flows and Minimum Cuts in a Network =====
+This section continues analyzing the uses of the Ford-Fulkerson algorithm from page 344.
+We want to show that the algorithm returns the absolute maximum value for any flow in G; therefore we will use cuts to place more upper bounds than just C.  Dividing the nodes into two sets, A and B means that we can bound the maximum flow values on A and on B; a cut is therefore a partition of the vertex set into A and B where s is in A and t is in B.  The capacity of this partition is c(A,B) = sum_(e in A) c_e. v(f) \leq c(A,B).  Every flow is upper-bounded by the capacity of every cut, so the maximum flow is equal to the minimum cut. W can compute an s-t cut of minimum capacity in O(m) time since we can extend the algorithm easily.  There is a maximum flow where every flow is an integer, but this is not always the case for every flow.  We can prove the Max-Flow Min-Cut Theorem even for real numbers, but we work well with integers on this problem.  This section was easier to read and helped a bit with the Ford-Fulkerson algorithm, but I still don’t understand residual graphs.  (7/10)