Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 03:45] – [6.7 Sequence Alignment in Linear Space via Divide and Conquer] gouldc | courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 04:29] – [6.8 Shortest Paths in a Graph] gouldc | ||
---|---|---|---|
Line 49: | Line 49: | ||
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 // | 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 // | ||
- | I am having a difficult time wrapping my head around | + | We do this by incorporating divide-and-conquer principles into our algorithm. |
===== 6.8 Shortest Paths in a Graph ===== | ===== 6.8 Shortest Paths in a Graph ===== | ||
+ | This section is about finding the shortest path between two nodes in a directed graph. Each edge has a weight. If there are no negative cycles (cycles that decrease the total cost of the path), then we want to find the path from s -> t that minimizes total edge costs... the shortest path. | ||
+ | |||
+ | starting node s and destination node t with minimum total cost. Each edge in the graph has an associated weight. | ||
+ | This section is about using a memoized array to keep track of the shortest paths in a graph. The new method is contrasted with Dijkstra' |