Differences

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

--- courses:cs211:winter2011:journals:camille:chapter6 [2011/03/27 16:17] – [Section 7: Sequence Alignment in Linear Space via Divide and Conquer] cobbc
+++ courses:cs211:winter2011:journals:camille:chapter6 [2011/04/03 00:40] (current) – [Section 8: Shortest Paths in a Graph] cobbc
@@ Line 1: / Line 1: @@
-====== Chapter 5: Divide and Conquer ======
+====== Chapter 6: Dynamic Programming ======
 ==== Intro ====
@@ Line 86: / Line 86: @@
     * **Summary:**
+This section discusses how to find shortest paths in a graph that contains negative edge costs (Dijkstra's only works for graphs with only positive edge costs). First we'll have the problem of figuring out if the graph has a negative cycle (i.e. the sum of the edge costs around the cycle is negative). Then we will find the shortest path P from s to t if the graph has no negative cycles. Things that don't work: Dijkstra's Algorithm no longer works (it greedily takes the edge of least cost out of the start node, but that path might be more expensive than a path that starts with a more costly edge but is compensated for by a negative cost edge later in the path), modifying the costs by adding a constant to them also doesn't work (you add more overall cost to longer paths from s to t than shorter paths, also see counterexample from class). The Bellman-Ford Algorithm uses dynamic programming to correctly find shortest paths. If G has no negative cycles, then there is a shortest path from s to t that is simple (i.e. doesn't repeat nodes), and hence has at most n-1 edges (p293). So we're going to try to find OPT(i,v), which is the optimal v-t path that uses at most i edges (so initially we'll be computing OPT(n-1,s)). Two choices: the path uses at most i-1 edges, in which case we're looking for OPT(i-1,v) or it uses i edges and the first edge is (v,w) so we're looking at a solution that is the cost of the (v,w) edge + OPT(i-1, w) ... for that one we'll have to consider all of the edges w that could be next out of v. They go into the algorithm. The running time is O(n^3) because there are the memoized table has n^2 entries, each of which could take O(n) time to compute. And then tracing back through to find the shortest path takes O(in) time where i is the number of edges in the path. They prove that you can put a tighter bound of O(mn) on the running time if there are significantly less edges than n^2. They then prove that you can significantly improve the space bound by only storing the shortest path from s to each node v instead of having the whole table. If we do this and also have each node maintain the first node on its path to t. There's also a chance that this can improve the running time of the algorithm, because you can stop when none of the entries in the array change in an iteration (but overall it doesn't affect the running time).
     * **Insights and Questions:**
+None really. I am curious about the other algorithm they mentioned that starts with the idea that subproblem i could be to find the shortest path using only i nodes ... which they say doesn't immediately work but can be made to work (but then they just switch to the Bellman-Ford Algorithm). It's also really interesting that this was one of the first applications of dynamic programming, but one of the last that we study
     * **Readability:**
+Awesome! I really enjoyed this section!
+===== Section 9: Shortest Paths and Distance Vector Protocols =====
+    * **Summary:**
+Routers in a communication network are an important application for the Shortest-Path problem. Nodes correspond to routers, and there is an edge between v and w if the two routers are connected directly. The cost is the delay on the link from one node to another. The problem is to find a path with minimum delay from a source node s to a destination t. Since the delays are definitely nonnegative, you could theoretically use Dijkstra's Algorithm, but that requires global knowledge of the network. The Bellman-Ford Algorithm doesn't ... each node just needs info from its neighbor (i.e. the length of the path to t from each node). To improve on Bellman-Ford, they propose switching from a pull-based algorithm (in each iteration, the nodes "pull" the value from their neighbors) to a push-based algorithm (none of those values "pulled" in the earlier algorithm change unless the node they're being pulled from has changed, so we will update the connected nodes when we change a value). Not all values need to be pushed each time, so running time is improved (a little). They give a concrete version of this algorithm and then discuss the real situation, where routers update at different speeds, so the algorithm runs asynchronously (a node that's values is changed becomes "active" until it has updated all of its values). The asynchronous version works, too. This algorithm computes shortest paths from a single source to a single destination, but in real life you'd be interested in distances from and to everything else, so they keep track of a distance vector protocol, which maintains a vector of distances to every other node in the network. There are a few problems with this approach. The algorithm assumes that edge costs remain the same and that edges are never deleted, but that's not true in real life. If an edge gets deleted, then cycles in the graph can just keep updating their information based on what's around them and never notice that the edge has been deleted (see the example from the slides). It's hard to tell if paths are just "down" or if they're really just disconnected. To avoid this problem, designers of network routing schemes used path vector protocols (store the whole path to everything else) instead of distance vector protocols. That way nodes can avoid the counting to infinity problem, but they require a lot more storage. The path vector protocol is used in the Border Gateway Protocol in the Internet core.
+    * **Insights and Questions:**
+How do nodes/paths get "added" in this algorithm? If we initially "know" which nodes are connected in order to figure out what needs to be "pushed" to, then, if something is added later, how do we tell the nodes that they need to push to this one? I guess we just update their list of things to push to ...
+    * **Readability:**
+As always, very easy to read :)