Chapter 6

• More general version of the greedy algorithms we worked on before.
• 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

• 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.

• 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

• 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

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

• 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

• 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

• 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

• 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

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

• 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