Differences

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

--- courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 02:54] – [6.6 Sequence Alignment] gouldc
+++ courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 04:41] – [6.8 Shortest Paths in a Graph] gouldc
@@ Line 45: / Line 45: @@
 (6.16) //OPT(i,j) = min(mismatch_cost(xi,yi) + OPT(i-1,j-1), gap_cost + OPT(i-1,j), gap_cost + OPT(i,j-1))//
-This is because there are three possibilities for the mth letter in string 1 and the nth letter in string 2: they form a pair in the optimal alignment, the mth letter in string 1 is not in any pair in the optimal alignment, or the nth letter in string 2 is not in any pair in the optimal alignment.
+This is because there are three possibilities for the mth letter in string 1 and the nth letter in string 2: they form a pair in the optimal alignment, the mth letter in string 1 is not in any pair in the optimal alignment, or the nth letter in string 2 is not in any pair in the optimal alignment. The dynamically programmed algorithm for this problem runs in O(mn) time because every pair (i,j) must be considered from 1...m and 1...n, and each of these takes at most constant time. It also takes O(mn) space.
 ===== 6.7 Sequence Alignment in Linear Space via Divide and Conquer =====
+This section shows us an improved algorithm for sequence alignment. It still runs in O(mn) time but it decreases the space requirement from O(mn) to O(m+n). We realize that computing a single column in the memoized array in the last problem only requires us to know about the current column and the previous column. Therefore it is possible to arrive at the solution while only maintaining a m-by-2 array instead of a m-by-n array. This idea will work nicely for building up to the solution //value// (i.e., the total cost of all gaps and mismatches)... but we also want to know the optimal //sequence// itself.
+We do this by incorporating divide-and-conquer principles into our algorithm. I'm slightly confused by the divide-and-conquer component to this problem. In class we did it with the graph in Figure 6.19. We started in the top left and found the shortest path to some midpoint, then we did the same thing from the bottom right. I will need to look in more depth at the pseudo-code on page 288 to get a better grasp of the concept.
 ===== 6.8 Shortest Paths in a Graph =====
+Shortest path in a directed graph where negative edges are possible. For this reason Dijkstra's Algorithm doesn't always work. (We cannot grow the blob, but we can build up partial solutions under the constraint that we can only use i edges.) In this problem we assume there are no negative cycles (cycles that decrease the total cost of the path); otherwise you could follow the cycle infinitely many times and reduce the cost to negative infinity.
+We want the path from s -> t that minimizes the total edge costs but that uses at most i edges. (6.22) says that the longest possible optimal path has n-1 edges.
+(6.23) //OPT(i,v) = min(OPT(i-1,v), min_w(OPT(i-1,w) + cw))//