Differences

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

--- courses:cs211:winter2011:journals:andrew:chapter6 [2011/03/14 20:42] – created bennetta
+++ courses:cs211:winter2011:journals:andrew:chapter6 [2011/04/05 23:24] (current) – bennetta
@@ Line 5: / Line 5: @@
    * Dynamic programming solution: a recurrence equation that expresses the optimal solution (or its value) in terms of the optimal solutions to smaller sub-problems
    * Memoization:
      * Saving values that have already been computed to reduce run time.
+     * Analysis on 257
+===== 6.2: Principles of Dynamic Programming: Memoization or Iteration over Subproblems =====
+   *Iterating over subproblems instead of computing solutions recursively
+   * Deals with using the array M from the Memoization/Recursion answer
+   * We can directly compute the entries in M by an iterative algorithm, rather than using memoized recursion.
+   * Analysis on 259.
+   * Second approach to dynamic programming: iterative building up of subproblems
+   * Subproblems for this approach my satisfy the following properties:
+     * There are only a polynomial number of subproblems
+     * The solution to the original problem can be easily computed from the solutions to the subproblems
+     * There is a natural ordering on the subproblems from "smallest" to "largest" together with an easy-to-compute recurrence that allows one to determine the solution to a subproblem from the solutions to some number of smaller subproblems.
+===== 6.3: Segmented Least Squares: Multi-way Choices =====
+   *Multi-way choices instead of binary choices
+   *Deals with plotting lines between points
+   *Penalty of a partition:
+     * The number of segments into which we partition P, times a fixed, given multiplier C>0 plus the error value of the optimal line through each segment
+   * Design and analysis of this segmented least squares problem can be found from 264-266
+===== 6.4: Subset Sums and Knapsacks: Adding a Variable =====
+   * Given a set of items, each with a given weight w and a bound for how much we can carry W
+   * Knapsack problem: Find a set of items that maximizes value and weight.
+   * Creation and analysis of the optimal algorithm for the knapsack problem begins on page 269 through page 271
+   * Knapsack problem can be solved in O(nW) time where n is the number of items that can be put in the sack and W is the weight
+===== 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