Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:david:chapter6 [2011/03/15 23:42] โ [6.2 - Principles of Dynamic Programming: Memoization or Iteration over Subproblems] margoliesd | courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:26] (current) โ [6.10 - Negative Cycles in a Graph] margoliesd | ||
---|---|---|---|
Line 16: | Line 16: | ||
Readability: | Readability: | ||
+ | |||
+ | ====6.3 - Segmented Least Squares: Multi-way Choices==== | ||
+ | |||
+ | We are trying to solve the problem of finding the line or lines of best fit for a set of (x,y) pairs, where each additional line adds a fixed cost to our overall penalty (which includes the squared errors). We note that the last point (ordered by x-coordinate) must belong to some segment of the graph that begins with another point. Once we know the first point in the segment, we can remove that segment and only consider what's left. Computing all the error values runs in O(n< | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.4 - Subset Sums and Knapsacks: Adding a Variable==== | ||
+ | |||
+ | The problem we consider here is of a single knapsack that can carry only a certain weight. We have items with weights that need to be added to the knapsack so as to get as close to the maximum weight as possible. The problem can be extended by giving each item a value, and we look for a solution that gives us maximum total value while still staying under the weight limit. We note that if we have an item " | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.5 - RNA Secondary Structure: Dynamic Programming over Intervals==== | ||
+ | |||
+ | This problem involves adding another variable to our problem. This occurs when we have a set of subproblems on {1,2,...,j} and we cannot find a natural recurrence, but we are able to find a natural recurrence on subproblems {i, | ||
+ | |||
+ | Our first attempt at a solution is that the opt(j)=0 for j less than or equal to 5. Otherwise, j is either unpaired, or paired with a base t such that t<j-4. This gives us two subproblems. Because we have the no crossing condition, this gives us two subproblems: | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.6 - Sequence Alignment==== | ||
+ | |||
+ | The problem we are trying to solve is how to determine how alike two words or sequences are. We will use gaps and mismatches to determine the optimal value, where gaps all have constant cost and mismatches have variable cost depending on the symbols mismatched. Thus, the cost of M, our optimal solution, is the total of all gaps and mismatch costs, which is the lowest in the optimal solution. We define our sets as Y={1, | ||
+ | |||
+ | Readability 5/10. This was another difficult section to understand. | ||
+ | |||
+ | ====6.7 - Sequence Alignment in Linear Space via Divide and Conquer==== | ||
+ | |||
+ | The space requirement in the previous section is O(mn), but this can become 10 GB if both strings are 100,000 symbols each. We find that we can use a divide and conquer approach to divide the problem in many recursive calls, which allows for space to be reused by each subsequent call. First, we note that we could use a 2-dimension array with the previous algorithm because we only need to know about the current and previous columns. However, this will not give us enough information to get the alignment back once we find its value. We use the graph from the previous section, and define g(i,j) as the length of the shortest path from (i,j) to (m,n). In our case, we initially start at g(m,n) which is 0, and try to find g(0,0), which gives the value. We call this the Backward-Space-Efficient-Alignment, | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.8 - Shortest Paths in Graphs==== | ||
+ | |||
+ | We will denote our directed graph as G=(V,E) and give each edge a specific weight. While Dijkstra' | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.9 - Shortest Paths and Distance Vector Protocols==== | ||
+ | |||
+ | An application for Shortest Paths algorithm we used in the previous section is for a network of routers (nodes) with direct links (edges). The cost of an edge is the delay of the link and we look for a path with the shortest delay. While Dijkstra' | ||
+ | |||
+ | Readability: | ||
+ | |||
+ | ====6.10 - Negative Cycles in a Graph==== | ||
+ | |||
+ | If we augment a graph by adding a sink node that has a path from every other node leading to it and the augmented graph has a negative cycle, then the original graph must have a negative cycle too. If we have a negative cycle and we are looking for a path from one node to the sink that passes through the cycle, as we increase the number of allowable edges, the cycle tends toward negative infinity. However, if there are no negative cycles, then opt(i, | ||
+ | |||
+ | Readability: |