Differences

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

--- courses:cs211:winter2011:journals:andrew:chapter6 [2011/03/14 21:01] – bennetta
+++ courses:cs211:winter2011:journals:andrew:chapter6 [2011/04/05 23:24] (current) – bennetta
@@ Line 34: / Line 34: @@
 ===== Final Thoughts (End of Chap 5, Beg of 6) =====
 This chapter is a little bit more easily understood than last weeks chapter. All in all, the knapsack problem is very intuitive and so is the idea of dynamic programming. Readability: 7/10
+===== 6.5: RNA Secondary Structure: Dynamic Programming over Intervals =====
+   * Adding a second variable to consider a subproblem for every contiguous interval in {1,2,...,n}
+   * RNA secondary structure prediction is a great example of this problem.
+   * Secondary structure occurs when RNA loops back and forms pairs with itself.
+   * Design of an algorithm to predict secondary structure of RNA can be found from 275-278
+===== 6.6: Sequence Alignment =====
+   *How do we define similarity between two words or strings?
+   *Strings can also arise in Biology - chromosomes
+   *Whole field of computational biology that deals with this
+   *First - parameter that defines a gap penalty
+   *Second- for each pair of letters p,q in the alphabet there is a mismatch cost for lining up p with q.
+   *The cost of alignment M is the sum of its gap and mismatch costs.
+   *Design of this algorithm starts on page 281
+===== 6.7: Sequence Alignment in Linear Space via Divide and Conquer =====
+   * Must get around the O(mn) space requirement
+   * This chapter covers making it work in O(mn) time using O(m + n) space
+   * Page 285-290 covers the design and analysis of this algorithm
+===== 6.8: Shortest Paths in a Graph =====
+   *This is the section I understand the most.
+   *Deals with finding the shortest path in a graph with negative edges.
+   *Minimum - Cost Path Problem and the Shortest-Path Problem
+   *Negative cycles can be seen as good arbitrage opportunities
+   *We can modify Dijkstra's Algorithm with some dynamic programming to create a solution to this problem.
+   *The design, analysis, and implementation of this algorithm starts on page 291
+===== 6.5-6.8 Final Words =====
+This is a section that I did not understand too particularly well both in the book and in class. The shortest path portion was probably my strongest area but I'm struggling a little bit with this material. Glad I did this journal on Monday so I know to get some extra help on this material before the problem set is due on Friday. Readability: 5/10
+===== 6.9: Shortest Paths and Distance Vector Protocols =====
+   *Shortest Paths algorithm can be applied to routers in a communication network to determine the most efficient path.
+     * Nodes are routers and edges are direct paths between these routers.
+     * Find minimum delay from a source node s to a destination node t.
+     * Cannot use Dijkstra's because it requires global knowledge.
+     * Bellman-Ford give us the best option
+     * Use a "push-based" algorithm rather than the "pull-based" algorithm of the original Bellman-Ford
+     * This pushed based method can be seen on page 298 and an Asynchronous version can be found on page 299\
+     * Problems:
+       * Assumes edge costs will remain constant
+       * Can cause counting to infinity
+     * For this reason path vector protocols are better than distance vector protocols