While we have seen cases where greedy algorithms can work, there are cases such that no greedy algorithm will work for a problem. Divide and conquer is another approach that we can use, but it is difficult to get from a problem with an exponential brute force solution to one with polynomial time. Dynamic programming involves dividing a problem into smaller and smaller subproblems, and then “building up” these solutions for larger subproblems until we get back to the original problem. Because we do not look at every possible solution, our dynamic programming solutions should perform better than their brute force counterparts.

Readability: 9/10

The weighted interval scheduling problem can be defined as follows: given a single resource and intervals with certain weights that would like to be scheduled on that resource, can we find a solution that optimizes the total weight while also having zero overlaps? To solve this problem, we assume we have the intervals ordered by increasing finish time. When considering an optimal solution to this problem, we know that such an optimal solution either contains the last interval or it does not. If it does not, then the optimal solution is simply the optimal solution of all other intervals. We use recursion to write this algorithm, but discover that we will be recomputing the “opt” for the same interval many times. To solve this, we store each optimal solution for an interval in a memoized array so that we do not need to recompute things. This gives us O(n) efficiency assuming the intervals come presorted. The best way to find the actual intervals then, is not by keeping track as we go through the algorithm, but by going through our memoized array after we are done. This is also O(n) efficiency.

Readability: 7/10

Because we can find our optimal solution by using the memoized array, we can create this array iteratively instead of recursively. That is, we solve the smallest subproblem before moving on to bigger subproblems. Then when we need to see if the solution to the current subproblem is better than the solution to the subproblem not including the current entry, we can just look it up in the memoized array. There are some conditions for which dynamic programming on a problem is possible: the number of subproblems should be polynomial, we need to be able to get our solution to the large problem easily by using the subproblems, and the subproblems need to be able to be ordered in some way from a smallest to a largest.

Readability: 8/10

We are trying to solve the problem of finding the line or lines of best fit for a set of (x,y) pairs, where each additional line adds a fixed cost to our overall penalty (which includes the squared errors). We note that the last point (ordered by x-coordinate) must belong to some segment of the graph that begins with another point. Once we know the first point in the segment, we can remove that segment and only consider what's left. Computing all the error values runs in O(n³) time, and filling in the memoized array takes O(n²) time.

Readability: 6/10. This was a difficult algorithm to understand.

The problem we consider here is of a single knapsack that can carry only a certain weight. We have items with weights that need to be added to the knapsack so as to get as close to the maximum weight as possible. The problem can be extended by giving each item a value, and we look for a solution that gives us maximum total value while still staying under the weight limit. We note that if we have an item “n” that is not in the optimal solution, then the optimal solution is opt(n-1,W). But if “n” is in the optimal solution, then our optimal solution becomes the w_n + opt(n-1,W-w_n). We use a two dimensional array M[n,W] for our memoization. The running time of the algorithm involving only weights in O(n). If we used the extended problem of considering values with items, we get a similar problem with a running time of O(nW). This means our running time is based not only on the number of items, but on the total weight allowed.

Readability: 7/10

This problem involves adding another variable to our problem. This occurs when we have a set of subproblems on {1,2,…,j} and we cannot find a natural recurrence, but we are able to find a natural recurrence on subproblems {i,i+1,…,j} for i less than or equal to j. The RNA secondary structure prediction is one such problem. We must match bases of {A,C,G,U} such that each pair is separated by at least four bases, all pairs must be either A-U or C-G, no base appears in more than one pair, and base pairs do not cross one-another.

Our first attempt at a solution is that the opt(j)=0 for j less than or equal to 5. Otherwise, j is either unpaired, or paired with a base t such that t<j-4. This gives us two subproblems. Because we have the no crossing condition, this gives us two subproblems: one one the bases up to t-1 and the other on the bases from t+1 to j-1. This is problematic because the second case is not solved by our subproblem. This forces us to add a variable so that we can begin subproblems starting with i instead of 1. We now find that opt(i,j) is the maximum of {opt(,j-1), max(1+opt(i,t-1)+opt(t+1,j-1))}. Our algorithm runs on O(n²) subproblems, which each take O(n) time so we get O(n³).

Readability: 5/10. This is a difficult problem to understand.

The problem we are trying to solve is how to determine how alike two words or sequences are. We will use gaps and mismatches to determine the optimal value, where gaps all have constant cost and mismatches have variable cost depending on the symbols mismatched. Thus, the cost of M, our optimal solution, is the total of all gaps and mismatch costs, which is the lowest in the optimal solution. We define our sets as Y={1,2,..,n} and X={1,2,..,m}, and note that for the optimal M, either (m,n) are in M (they match), or they do not. This leads us to the following recurrence, where either 1,2,or 3 is true. 1 - (m,n) is in M, 2 - the m^th position of X is not matched, 3 - the n^th position of Y is not matched. This gives us opt(i,j) as min[mismatch cost of x_i,y_j + opt(i-1,j-1), gap cost + opt(i-1,j), gap cost + opt(i,j-1)]. There is also a pictoral approach involving the minimum cost path. We get a running time of O(mn).

Readability 5/10. This was another difficult section to understand.

The space requirement in the previous section is O(mn), but this can become 10 GB if both strings are 100,000 symbols each. We find that we can use a divide and conquer approach to divide the problem in many recursive calls, which allows for space to be reused by each subsequent call. First, we note that we could use a 2-dimension array with the previous algorithm because we only need to know about the current and previous columns. However, this will not give us enough information to get the alignment back once we find its value. We use the graph from the previous section, and define g(i,j) as the length of the shortest path from (i,j) to (m,n). In our case, we initially start at g(m,n) which is 0, and try to find g(0,0), which gives the value. We call this the Backward-Space-Efficient-Alignment, and it has a space requirement of O(m+n) and a running time of O(mn).

Readability: 5/10. Another difficult section.

We will denote our directed graph as G=(V,E) and give each edge a specific weight. While Dijkstra's Algorithm can find us the path of least cost, it does not work for negative costs. Our problem involves finding the path of least cost in a graph that can have negative edge weights, but does not have any negative cycles. If we begin with a greedy approach, we consider the minimum cost edge leaving our node. But this could cause us to miss an edge of greater cost that leads us on a path with more negative costs that could negate it. The Bellman-Ford Algorithm gives an efficient solution to our problem. We note that our path will have at most n-1 edges. If we define opt(i,v) to be the minimum cost of the path from to v to t with at most i edges, we can definite is as the minimum of [opt(i-1,v), min(opt(i-1,w) + the cost of v to w). This gives a 2-dimensional array M with the optimal values for each subproblem. We can get a running time of O(mn). While our array will be of size n², we can actually get a smaller memory requirement. We use a 1-dimensional array and only update a cost if it was lower than the previous cost. We keep a “first” node for each entry to keep track of the first edge we need to take. This will allow us to find the optimal path after the algorithm has completed.

Readability: 8/10. This was easier to understand than the other sections.

An application for Shortest Paths algorithm we used in the previous section is for a network of routers (nodes) with direct links (edges). The cost of an edge is the delay of the link and we look for a path with the shortest delay. While Dijkstra's Algorithm could work in this situation because delays cannot be negative, it requires us to have a global knowledge of the network. We can use Bellman-Ford to avoid this problem, but we need to re-implement it as a “push-based” algorithm where costs need only be sent if they change value. We use an “asynchronous” algorithm to denote which nodes are active so we can update its neighbors. We call the finding of distances between all pairs of nodes a “distance vector protocol”. One problem with this algorithm occurs if an edge gets deleted. Then our nodes keep referring back to each other until they find a new path. In practice, nodes store more of the entire path so we do not have this problem.

Readability: 7/10.

If we augment a graph by adding a sink node that has a path from every other node leading to it and the augmented graph has a negative cycle, then the original graph must have a negative cycle too. If we have a negative cycle and we are looking for a path from one node to the sink that passes through the cycle, as we increase the number of allowable edges, the cycle tends toward negative infinity. However, if there are no negative cycles, then opt(i,v)=opt(n-1,v) as long as i is greater than or equal to n. So as long as this holds true for all nodes, there are no negative cycles in the graph. We can use a pointer graph that starts off having no cycles and add edges to it until we find a cycle.

Readability: 5/10. The last part confused me.