Design and Analysis of Algoirthms 5

UNIT - 2

Dynamic programming

In mathematics, management science, economics, computer science, and bioinformatics, dynamic programming (also known as dynamic optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions – ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The technique of storing solutions to subproblems instead of recomputing them is called "memoization".

Dynamic programming algorithms are often used for optimization. A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. In comparison, a greedy algorithm treats the solution as some sequence of steps and picks the locally optimal choice at each step. Using a greedy algorithm does not guarantee an optimal solution, because picking locally optimal choices may result in a bad global solution, but it is often faster to calculate. Fortunately, some greedy algorithms (such as Kruskal's or Prim's for minimum spanning trees) are proven to lead to the optimal solution.

For example, in the coin change problem of finding the minimum number of coins of given denominations needed to make a given amount, a dynamic programming algorithm would find an optimal solution for each amount by first finding an optimal solution for each smaller amount and then using these solutions to construct an optimal solution for the larger amount. In contrast, a greedy algorithm might treat the solution as a sequence of coins, starting from the given amount and at each step subtracting the largest possible coin denomination that is less than the current remaining amount. If the coin denominations are 1,4,5,15,20 and the given amount is 23, this greedy algorithm gives a non-optimal solution of 20+1+1+1, while the optimal solution is 15+4+4.

Dijkstra's algorithm for the shortest path problem[edit]

From a dynamic programming point of view, Dijkstra's algorithm for the shortest path problem is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.^[6][7][8]

In fact, Dijkstra's explanation of the logic behind the algorithm,^[9] namely

Problem 2. Find the path of minimum total length between two given nodes ${\displaystyle P}$ and ${\displaystyle Q}$.

We use the fact that, if ${\displaystyle R}$ is a node on the minimal path from ${\displaystyle P}$ to ${\displaystyle Q}$, knowledge of the latter implies the knowledge of the minimal path from ${\displaystyle P}$ to ${\displaystyle R}$.

is a paraphrasing of Bellman's famous Principle of Optimality in the context of the shortest path problem.

Fibonacci sequence[edit]

This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (May 2013) (Learn how and when to remove this template message)

Here is a naïve implementation of a function finding the nth member of the Fibonacci sequence, based directly on the mathematical definition:

   function fib(n)
       if n <= 1 return n
       return fib(n − 1) + fib(n − 2)

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

In particular, fib(2) was calculated three times from scratch. In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time algorithm.

Now, suppose we have a simple map object, m, which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O(n) time instead of exponential time (but requires O(n) space):

   var m := map(0 → 0, 1 → 1)
   function fib(n)
       if key n is not in map m 
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.

In the bottom-up approach, we calculate the smaller values of fib first, then build larger values from them. This method also uses O(n) time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the map.

   function fib(n)
       if n = 0
           return 0
       else
           var previousFib := 0, currentFib := 1
           repeat n − 1 times // loop is skipped if n = 1
               var newFib := previousFib + currentFib
               previousFib := currentFib
               currentFib  := newFib
       return currentFib

In both examples, we only calculate fib(2) one time, and then use it to calculate both fib(4) and fib(3), instead of computing it every time either of them is evaluated.

Note that the above method actually takes ${\displaystyle \Omega (n^{2})}$ time for large n because addition of two integers with ${\displaystyle \Omega (n)}$ bits each takes ${\displaystyle \Omega (n)}$ time. (The n^th fibonacci number has ${\displaystyle \Omega (n)}$ bits.) Also, there is a closed form for the Fibonacci sequence, known as Binet's formula, from which the ${\displaystyle n}$-th term can be computed in approximately ${\displaystyle O(n(\log n)^{2})}$ time, which is more efficient than the above dynamic programming technique. However, the simple recurrence directly gives the matrix form that leads to an approximately ${\displaystyle O(n\log n)}$ algorithm by fast matrix exponentiation.

[https://en.wikipedia.org/wiki/Dynamic_programming]

Dynamic programming is a fancy name for using divide-and-conquer technique with a table. As compared to divide-and-conquer, dynamic programming is more powerful and subtle design technique. Let me repeat , it is not a specific algorithm, but it is a meta-technique (like divide-and-conquer). This technique was developed back in the days when "programming" meant "tabular method" (like linear programming). It does not really refer to computer programming. Here in our advanced algorithm course, we'll also think of "programming" as a "tableau method" and certainly not writing code. Dynamic programming is a stage-wise search method suitable for optimization problems whose solutions may be viewed as the result of a sequence of decisions. The most attractive property of this strategy is that during the search for a solution it avoids full enumeration by pruning early partial decision solutions that cannot possibly lead to optimal solution. In many practical situations, this strategy hits the optimal solution in a polynomial number of decision steps. However, in the worst case, such a strategy may end up performing full enumeration.

Dynamic programming takes advantage of the duplication and arrange to solve each subproblem only once, saving the solution (in table or in a globally accessible place) for later use. The underlying idea of dynamic programming  is: avoid calculating the same stuff twice, usually by keeping a table of known results of subproblems. Unlike divide-and-conquer, which solves the subproblems top-down, a dynamic programming is a bottom-up technique. The dynamic programming technique is related to divide-and-conquer, in the sense that it breaks problem down into smaller problems and it solves recursively. However, because of the somewhat different nature of dynamic programming problems, standard divide-and-conquer solutions are not usually efficient.

The dynamic programming is among the most powerful for designing algorithms for optimization problem. This is true for two reasons. Firstly, dynamic programming solutions are based on few common elements. Secondly, dynamic programming problems are typical optimization problems i.e., find the minimum or maximum cost solution, subject to various constraints.

In other words, this technique used for optimization problems:

• Find a solution to the problem with the optimal value.
• Then perform minimization or maximization. (We'll see example of both in CLRS).

The dynamic programming is a paradigm of algorithm design in which an optimization problem is solved by a combination of caching subproblem solutions and appealing to the "principle of optimality."

There are three basic elements that characterize a dynamic programming algorithm:

1. Substructure

Decompose the given problem into smaller (and hopefully simpler) subproblems. Express the solution of the original problem in terms of solutions for smaller problems. Note that unlike divide-and-conquer problems, it is not usually sufficient to consider one decomposition, but many different ones.

2. Table-Structure

After solving the subproblems, store the answers (results) to the subproblems in a table. This is done because (typically) subproblem solutions are reused many times, and we do not want to repeatedly solve the same problem over and over again.

3. Bottom-up Computation

Using table (or something), combine solutions of smaller subproblems to solve larger subproblems, and eventually arrive at a solution to the complete problem. The idea of bottom-up computation is as follow:

Bottom-up means

1. Start with the smallest subproblems.
2. Combining theirs solutions obtain the solutions to subproblems of increasing size.
3. Until arrive at the solution of the original problem.

Once we decided that we are going to attack the given problem with dynamic programming technique, the most important step is the formulation of the problem. In other words, the most important question in designing a dynamic programming solution to a problem is how to set up the subproblem structure.

If I can't apply dynamic programming to all optimization problem, then the question is what should I look for to apply this technique? Well! the answer is there are two important elements that a problem must have in order for dynamic programming technique to be applicable (look for those!).

1. Optimal Substructure  

Show that a solution to a problem consists of making a choice, which leaves one or sub-problems to solve. Now suppose that you are given this last choice to an optimal solution. [Students often have trouble understanding the relationship between optimal substructure and determining which choice is made in an optimal solution. One way to understand optimal substructure is to imagine that "God" tells you what was the last choice made in an optimal solution.] Given this choice, determine which subproblems arise and how to characterize the resulting space of subproblems. Show that the solutions to the subproblems used within the optimal solution must themselves be optimal (optimality principle). You usually use cut-and-paste:

• Suppose that one of the subproblem is not optimal.
• Cut it out.
• Paste in an optimal solution.
• Get a better solution to the original problem. Contradicts optimality of problem solution.

That was optimal substructure.

You need to ensure that you consider a wide enough range of choices and subproblems that you get them all . ["God" is too busy to tell you what that last choice really was.] Try all the choices, solve all the subproblems resulting from each choice, and pick the choice whose solution, along the subproblem solutions, is best.

We have used "Optimality Principle" a couple of times. Now a word about this beast: The optimal solution to the problem contains within it optimal solutions to subproblems. This is some times called the principle of optimality.

The Principle of Optimality

The dynamic programming  relies on a principle of optimality. This principle states that in an optimal sequence of decisions or choices, each subsequence must also be optimal. For example, in matrix chain multiplication problem, not only the value we are interested in is optimal but all the other entries in the table are also represent optimal. The principle can be related as follows: the optimal solution to a problem is a combination of optimal solutions to some of its subproblems. The difficulty in turning the principle of optimally into an algorithm is that it is not usually obvious which subproblems are relevant to the problem under consideration.

Now the question is how to characterize the space of subproblems?

• Keep the space as simple as possible.
• Expand it as necessary.

As an example, consider the assembly-line scheduling. In this problem, space of subproblems was fastest way from factory entry through stations S_1, j  and S_2, j. Clearly, no need to try a more general space of subproblems. On the hand, in case of optimal binary search trees. Suppose we had tried to constrain space of subproblems to subtrees with keys k₁, k₂, . . . , k_j. An optimal BST would have root k_r , for some 1 ≤ r ≤ j. Get subproblems k₁, . . . , k_{r − 1} and k_{r + 1}, . . . , k_j. Unless we could guarantee that r = j, so that subproblem with k_{r + 1}, . . . , k_j is empty, then this subproblem is not of the form k₁, k₂, . . . , k_j. Thus, needed to allow the subproblems to vary at both ends, i.e., allow both i and j to vary.

Optimal substructure varies across problem domains:

1. How many subproblems are used in an optimal solution.
2. How many choices in determining which subproblem(s) to use.

In Assembly-line Scheduling Problem: we have 1 subproblem and 2 choices (for S_i, j use either S_{1, j − 1} or S_{2, j − 1}). In the Longest Common Subsequence Problem: we have 1 subproblem but as far as choices are concern, we have either 1 choice (if x_i = y_j , LCS of X_{i − 1} and Y_{j − 1}), or 2 choices (if x_i = y_j , LCS of X_{i − 1} and Y , and LCS of X and Y_{j − 1}). Finally, in case of the Optimal Binary Search Tree Problem: we have 2 subproblems (k_i , . . . , k_{r − 1} and k_{r + 1}, . . . , k_j) and j − i + 1 choices for k_r in k_i, . . . , k_j . Once we determine optimal solutions to subproblems, we choose from among the j − i + 1 candidates for k_r .

Informally, the running time of the dynamic programming algorithm depends on the overall number of subproblems times the number of choices. For example, in the assembly-line scheduling problem, there are Θ(n) subproblems and 2 choices for each implying running time is Θ(n). In case of longest common subsequence problem, there are Θ(mn) subproblems and at least 2 choices for each implying Θ(mn) running time. Finally, in case of optimal binary search tree problem, we have Θ(n²) sub-problems and Θ(n) choices for each implying Θ(n³) running time.

Dynamic programming uses optimal substructure bottom up fashion:

• First find optimal solutions to subproblems.
• Then choose which to use in optimal solution to the problem.

When we look at greedy algorithms, we'll see that they work in top down fashion:

• First make a choice that looks best.
• Then solve the resulting subproblem.

Warning! You'll surely make an ass out of yourself into thinking optimal substructure applies to all optimization problems. IT DOES NOT. Let me repeat, dynamic programming is not applicable to all optimization problems.
To see this point clearly, go through pages 341 − 344 of CLRS where authors discussed two problems that look similar: Shortest Path Problem and Longest Simple Path Problem. In both problems, they gave us an unweighted, directed graph G = (V, E). And our job is to find a path (sequence of connected edges) from vertex u in V to vertex v in V.

Subproblems Dependencies

It is easy to see that the subproblems, in our above examples, are independent subproblems: For example, in the assembly line problem, there is only 1 subproblem so it is trivially independent. Similarly, in the longest common subsequence problem, again we have only 1 subproblem thus it is automatically independent. On the other hand, in the optimal binary search tree problem, we have two subproblems, k_i, . . . , k_{r − 1} and k_{r + 1}, . . . , k_j, which are clearly independent.

2. Polynomially many (Overlapping) Subproblems

An important aspect to the efficiency of dynamic programming is that the total number of distinct sub-problems to be solved should be at most a polynomial number. Overlapping subproblems occur when recursive algorithm revisits the same problem over and over. A good divide-and-conquer algorithm, for example the merge-sort algorithm, usually generate a brand new problem at each stage of recursion. Our Textbook CLRS has a good example for matrix-chain multiplication to depict this idea. The CLRS also talked about the alternative approach so-called memoization. It works as follows:

• Store, don't recompute
• Make a table indexed by subproblem.
• When solving a subproblem:
  • Lookup in the table.
  • If answer is there, use it.
  • Otherwise, compute answer, then store it.

In dynamic programming, we go one step further. We determine in what order we would want to access the table, and fill it in that way.

Four-Step Method of CLRS

Our Text suggested that the development of a dynamic programming algorithm can be broken into a sequence of following four steps.

1. Characterize the structure of an optimal solution.
2. Recursively defined the value of an optimal solution.
3. Compute the value of an optimal solution in a bottom-up fashion.
4. Construct an optimal solution from computed information.

[http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/dynamicIntro.htm]

Matrix-chain Multiplication  Problem

The chain matrix multiplication problem is perhaps the most popular example of dynamic programming used in the upper undergraduate course (or review basic issues of dynamic programming in advanced algorithm's class).

The chain matrix multiplication problem involves the question of determining the optimal sequence for performing a series of operations. This general class of problem is important in complier design for code optimization and in databases for query optimization. We will study the problem in a very restricted instance, where the dynamic programming issues are clear. Suppose that our problem is to multiply a chain of n matrices A₁ A₂ ... A_n. Recall (from your discrete structures course), matrix multiplication is an associative but not a commutative operation. This means that you are free to parenthesize the above multiplication however we like, but we are not free to rearrange the order of the matrices. Also, recall that when two (non-square) matrices are being multiplied, there are restrictions on the dimensions.

Suppose, matrix A has p rows and q columns i.e., the dimension of matrix A is p × q. You can multiply a matrix A of p × q dimensions times a matrix B of dimensions q × r, and the result will be a matrix C with dimensions p × r. That is, you can multiply two matrices if they are compatible: the number of columns of A must equal the number of rows of B.

In particular, for 1 ≤ i ≤  p and 1 ≤ j ≤ r, we have

C[i, j] = ∑_{1 ≤ k ≤ q} A[i, k] B[k, j].

There are p . r total entries in C and each takes O(q) time to compute, thus the total time to multiply these two matrices is dominated by the number of scalar multiplication, which is p . q . r.

Problem Formulation

Note that although we can use any legal parenthesization, which will lead to a valid result. But, not all parenthesizations involve the same number of operations. To understand this point, consider the problem of a chain A₁, A₂, A₃ of three matrices and suppose

A₁ be of dimension 10 × 100
A₂ be of dimension 100 × 5
A₃ be of dimension 5 × 50

Then,

MultCost[((A₁ A₂) A₃)] = (10 . 100 . 5) +  (10 . 5 . 50) = 7,500 scalar multiplications.

MultCost[(A₁ (A₂ A₃))] = (100 . 5 . 50) + (10 . 100 . 50) = 75,000 scalar multiplications.

It is easy to see that even for this small example, computing the product according to first parenthesization is 10 times faster.

The Chain Matrix Multiplication Problem

Given a sequence of n matrices A₁, A₂, ... A_n, and their dimensions p₀, p₁, p₂, ..., p_n, where where i = 1, 2, ..., n, matrix A_i has dimension p_{i − 1} × p_i, determine the order of multiplication that minimizes the the number of scalar multiplications.

Equivalent formulation (perhaps more easy to work with!)

Given n matrices, A₁, A₂, ... A_n, where for 1 ≤ i ≤ n, A_i is a p_{i − 1} × p_i, matrix, parenthesize the product A₁, A₂, ... A_n so as to minimize the total cost, assuming that the cost of multiplying an p_{i − 1}× p_i matrix by a p_i × p_{i + 1} matrix using the naive algorithm is p_{i − 1}× p_i × p_{i + 1}.

Note that this algorithm does not perform the multiplications, it just figures out the best order in which to perform the multiplication operations.

Naive Algorithm

Well, lets start from the obvious! Suppose we are given a list of n matrices. lets attack the problem with brute-force and try all possible parenthesizations. It is easy to see that the number of ways of parenthesizing an expression is very large. For instance, if you have just one item in the list, then there is only one way to parenthesize. Similarly, if you have n item in the list, then there are n − 1 places where you could split the list with the outermost pair of parentheses, namely just after first item, just after the second item, and so on and so forth, and just after the (n − 1)^th item in the list.

On the other hand, when we split the given list just after the k^th item, we create two sublists to be parenthesized, one with k items, and the other with n − k items. After splitting, we could consider all the ways of parenthesizing these sublists (brute force in action). If there are L ways to parenthesize the left sublist and R ways to parenthesize the right sublist and since these are independent choices, then the total is Ltimes R. This suggests the following recurrence for P(n), the number of different ways of parenthesizing n items:

This recurrence is related to a famous function in combinatorics called the Catalan numbers, which in turn is related to the number of different binary trees on n nodes. The solution to this recurrence is the sequence of Catalan numbers. In particular P(n) = C(n − 1), where C(n) is the n^th Catalan number. And, by applying Stirling's formula, we get the lower bound on the sequence. That is,

since 4ⁿ is exponential and n^3/2 is just a polynomial, the exponential will dominate the expression, implying that function grows very fast. Thus, the number of solutions is exponential in n, and the brute-force method of exhaustive search is a poor strategy for determining the optimal parenthesization of a matrix chain. Therefore, the naive algorithm will not be practical except for very small n.

Dynamic Programming Approach

The first step of the dynamic programming paradigm is to characterize the structure of an optimal solution. For the chain matrix problem, like other dynamic programming problems, involves determining the optimal structure (in this case, a parenthesization). We would like to break the problem into subproblems, whose solutions can be combined to obtain a solution to the global problem.

For convenience, let us adopt the notation A_i .. j, where i ≤ j, for the result from evaluating the product  A_i A_{i + 1} ... A_j. That is,

A_i .. j ≡ A_i A_{i + 1} ... A_j ,    where i ≤ j,

It is easy to see that is a matrix A_i .. j  is of dimensions p_i × p_{i + 1}.

In parenthesizing the expression, we can consider the highest level of parenthesization. At this level we are simply multiplying two matrices together. That is, for any k, 1 ≤  k ≤  n − 1,

A_1..n = A_1..k  A_k+1..n .

Therefore, the problem of determining the optimal sequence of multiplications is broken up into two questions:

Question 1: How do we decide where to split the chain? (What is k?)   

Question 2: How do we parenthesize the subchains A_1..k  A_k+1..n?

The subchain problems can be solved by recursively applying the same scheme. On the other hand, to determine the best value of k, we will consider all possible values of k, and pick the best of them. Notice that this problem satisfies the principle of optimality, because once we decide to break the sequence into the product , we should compute each subsequence optimally. That is, for the global problem to be solved optimally, the subproblems must be solved optimally as well.

The key observation is that the parenthesization of the "prefix" subchain A_1..k within this optimal parenthesization of A_1..n. must be an optimal parenthesization of A_1..k.

Dynamic Programming Formulation

The second step of the dynamic programming paradigm is to define the value of an optimal solution recursively in terms of the optimal solutions to subproblems. To help us keep track of solutions to subproblems, we will use a table, and build the table in a bottom­up manner. For 1 ≤ i ≤ j ≤ n, let m[i, j] be the minimum number of scalar multiplications needed to compute the A_i..j. The optimum cost can be described by the following recursive formulation.

Basis: Observe that if i = j then the problem is trivial; the sequence contains only one matrix, and so the cost is 0. (In other words, there is nothing to multiply.) Thus,

m[i, i] = 0 for i = 1, 2, ..., n.

Step: If i ≠ j, then we are asking about the product of the subchain A_i..j and we take advantage of the structure of an optimal solution. We assume that the optimal parenthesization splits the product, A_i..j into for each value of k, 1 ≤  k ≤  n − 1 as A_i..k . A_k+1..j.

The optimum time to compute is m[i, k], and the optimum time to compute is m[k + 1, j]. We may assume that these values have been computed previously and stored in our array. Since A_i..k is a matrix, and A_k+1..j is a matrix, the time to multiply them is p_i − 1 . p_k . p_j. This suggests the following recursive rule for computing m[i, j].

To keep track of optimal subsolutions, we store the value of k in a table s[i, j]. Recall, k is the place at which we split the product A_i..j to get an optimal parenthesization. That is,

s[i, j] = k such that m[i, j] = m[i, k] + m[k + 1, j] + p_i − 1 . p_k . p_j.

Implementing the Rule

The third step of the dynamic programming paradigm is to construct the value of an optimal solution in a bottom-up fashion. It is pretty straight forward to translate the above recurrence into a procedure. As we have remarked in the introduction that the dynamic programming is nothing but the fancy name for divide-and-conquer with a table. But here in dynamic programming, as opposed to divide-and-conquer, we solve subproblems sequentially. It means the trick here is to solve them in the right order so that whenever the solution to a subproblem is needed, it is already available in the table.

Consequently, in our problem the only tricky part is arranging the order in which to compute the values (so that it is readily available when we need it). In the process of computing m[i, j] we will need to access values m[i, k] and m[k + 1, j] for each value of k lying between i and j. This suggests that we should organize our computation according to the number of matrices in the subchain. So, lets work on the subchain:

Let L = j − i + 1 denote the length of the subchain being multiplied. The subchains of length 1 (m[i, i]) are trivial. Then we build up by computing the subchains of length 2, 3, ..., n. The final answer is m[1, n].

Now set up the loop: Observe that if a subchain of length L starts at position i, then j = i + L − 1. Since, we would like to keep j in bounds, this means we want j ≤ n, this, in turn, means that we want i + L − 1 ≤ n, actually what we are saying here is that we want i ≤ n − L +1. This gives us the closed interval for i. So our loop for i runs from 1 to n − L + 1.

Matrix-Chain(array p[1 .. n], int n) {
          Array s[1 .. n − 1, 2 .. n];
          FOR i = 1 TO n DO m[i, i] = 0;                                         // initialize
          FOR L = 2 TO n DO {                                                      // L=length of subchain
                  FOR i = 1 TO n − L + 1 do {
                           j = i + L − 1;
                          m[i, j] = infinity;
                          FOR k = i TO j − 1 DO {                                  // check all splits
                                  q = m[i, k] + m[k + 1, j] + p[i − 1] p[k] p[j];
                                  IF (q < m[i, j]) {
                                          m[i, j] = q;
                                           s[i, j] = k;
                                  }
                           }
                   }
            }
           return m[1, n](final cost) and s (splitting markers);
           }

Example [on page 337 in CLRS]: The m-table computed by MatrixChain procedure for n = 6 matrices A₁, A₂, A₃, A₄, A₅, A₆ and their dimensions 30, 35, 15, 5, 10, 20, 25.

Note that the m-table is rotated so that the main diagonal runs horizontally. Only the main diagonal and upper triangle is used.

Complexity Analysis

Clearly, the space complexity of this procedure Ο(n²). Since the tables m and s require Ο(n²) space. As far as the time complexity is concern, a simple inspection of the for-loop(s) structures gives us a running time of the procedure. Since, the three for-loops are nested three deep, and each one of them iterates at most n times (that is to say indices L, i, and j takes on at most n − 1 values). Therefore, The running time of this procedure is Ο(n³).

Extracting Optimum Sequence

This is Step 4 of the dynamic programming paradigm in which we construct an optimal solution from computed information. The array s[i, j] can be used to extract the actual sequence. The basic idea is to keep a split marker in s[i, j] that indicates what is the best split, that is, what value of k leads to the minimum value of m[i, j]. s[i, j] = k tells us that the best way to multiply the subchain is to first multiply the subchain A_i..k and then multiply the subchain  A_k+1..j, and finally multiply these two subchains together. Intuitively, s[i, j] tells us what multiplication to perform last. Note that we only need to store s[i, j] when we have at least two matrices, that is, if j > i. The actual multiplication algorithm uses the s[i, j] value to determine how to split the current sequence. Assume that the matrices are stored in an array of matrices A[1..n], and that s[i, j] is global to this recursive procedure. The procedure returns a matrix.

Mult(i, j) {
       if (i = = j) return A[i];            // Basis
       else {
                   k = s[i, j];
                   X = Mult(i, k];          // X=A[i]…A[k]
                   Y = Mult(k + 1, j];     // Y=A[k+1]…A[j]
                    return XY;               // multiply matrices X and Y
              }
        }

Again, we rotate the s-table so that the main diagonal runs horizontally but in this table we use only upper triangle (and not the main diagonal).

In the example, the procedure computes the chain matrix product according to the parenthesization ((A₁(A₂ A₃))((A₄ A₅) A₆).

Recursive Implementation

Here we will implement the recurrence  in the following recursive procedure that determines m[i, j], the minimum number of scalar multiplications needed to compute the chain matrix product Ai..j. The recursive formulation have been set up in a top-down manner. Now consider the following recursive implementation of the chain­matrix multiplication algorithm. The call Rec­Matrix­Chain(p, i, j) computes and returns the value of m[i, j]. The initial call is Rec­Matrix­Chain(p, 1, n). We only consider the cost here.

Rec-Matrix-Chain(array p, int i, int j) {
      if (i = = j) m[i, i] = 0;                               // basic case
      else {
                  m[i, j] = infinity;                          // initialize
                  for k = i to j − 1 do {                   // try all possible splits
                           cost=Rec-Matrix-Chain(p, i, k) + Rec-Matrix-Chain(p, k + 1, j) + p[i − 1]*p[k]*p[j];
                           if (cost<m[i, j]) then
                                    m[i, j]= cost;
                           }
                   }                                               // update if better
       return m[i,j];                                          // return final cost
}

This version, which is based directly on the recurrence (the recursive formulation that we gave for chain matrix problem) seems much simpler. So, what is wrong with this? The answer is the running time is much higher than the algorithm that we gave before. In fact, we will see that its running time is exponential in n, which is unacceptably slow.

Let T(n) be the running time of this algorithm on a sequence of matrices of length n, where n = j − i + 1.

If i = j, then we have a sequence of length 1, and the time is Θ(1). Otherwise, we do Θ(1) work and then consider all possible ways of splitting the sequence of length n into two sequences, one of length k and the other of length n − k, and invoke the procedure recursively on each one. So, we get the following recurrence, defined for n ≥ 1.

Note that we have replaced the Θ(1)'s with the constant 1.

Claim: T(n) = 2^{n − 1}.

Proof. We shall prove by induction on n. This is trivially true for n = 1. (Since T(1) ≥ 1 = 2⁰.) Our induction hypothesis is that T(m) = 2^{m − 1}. for all m < n. Using this hypothesis, we have

T(n) = 1 + ∑_{1≤ k≤ n-1} (T(k) + T(n − k))

≥ 1 + ∑_{1≤ k≤ n-1} T(k)                      -- Ignore the term T(n − k).

≥ 1 + ∑_{1≤ k≤ n-1} (2^k −1)                  -- by application of induction hypothesis.

= 1 + ∑_{0≤ k≤ n-2} (2^k)                      -- By application of geometric series formula.

= 1 + (2^n −1 + 1)

= 2^n −1.

 Therefore, we have T(n) = Ω(2ⁿ).

Now the question is why this is so inefficient than that of bottom-up dynamic programming algorithm? If you "unravel'' the recursive calls on a reasonably long example, you will see that the procedure is called repeatedly with the same arguments. The bottom-up version evaluates each entry exactly once.

Memoization [I think this should be Memorization but lets stick to the textbook!]

Now from very practical viewpoint, we would like to have the nice top-down structure of recursive algorithm with the efficiency of bottom-up dynamic programming algorithm. The question is: is it possible? The answer is yes, using the technique called memoization.

The fact that our recursive algorithm runs in exponential time is simply due to the spectacular redundancy in the number of time it issues recursive calls. Now our problem is how could we eliminate all this redundancy? We could store the value of "cost" in a globally accessible place the first time we compute it and then simply use this precomputed value in place of all future recursive calls. This technique of saving values that have already been computed is referred to as memoization.

The idea is as follow. Let's reconsider the function Rec­Matrix­Chain() given above. It's job is to compute m[i, j], and return its value. The main problem with the procedure is that it recomputes the same entries over and over. So, we will fix this by allowing the procedure to compute each entry exactly once. One way to do this is to initialize every entry to some special value (e.g. UNDEFINED). Once an entries value has been computed, it is never recomputed.
In essence, what we are doing here is we are maintaining a table with subproblem solution (like dynamic programming algorithm), but filling up the table more like recursive algorithm. In other words, we would like to have best of both worlds!

Mem-Matrix-Chain(array p, int i, int j) {
         if (m[i, j] != UNDEFINED) then 
                   return m[i, j];                            // already defined
         else if ( i = = j) then
                      m[i, i] = 0;                                // basic case
                else {
                         m[i, j] = infinity;                    // initialize
                         for k = i to j − 1 do {               // try all splits
                               cost = Mem-Matrix-Chain(p, i, k) + Mem-Matrix-Chain(p, k + 1, j) + p[i − 1] p[k] p[j];
                               if (cost < m[i, j]) then      // update if better
                                   m[i, j] = cost;
                               }
                        }
         return m[i, j];                                      // return final cost
}

Like the dynamic programming algorithm, this version runs in time Ο(n³). Intuitively, the reason is this: when we see the subroblem for the first time, we compute its solution and store in the table. After that whenever we see the subproblem again, we simply looked up in the table and returned the solution. So, we are computing each of the Ο(n²) table entry once and, and the work needed to compute one table entry (most of it in the for­loop) is at most Ο(n). So, memoization turns an Ω(2ⁿ)-time algorithm into an time Ο(n³)-algorithm.

As a matter of fact, in general, Memoization is slower than bottom-up method, so it is not usually used in practice. However, in some dynamic programming problems, many of the table entries are simply not needed, and so bottom-up computation may compute entries that are never needed. In these cases, we use memoization to compute the table entry once. If you know that most of the table will not be needed, here is a way to save space. Rather than storing the whole table explicitly as an array, you can store the "defined" entries of the table in a hash table, using the index pair (i, j) as the hash key.

[http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/chainMatrixMult.htm]

Dynamic-Programming Algorithm

for the Activity-Selection Problem

An activity-selection is the problem of scheduling a resource among several competing activity.
 
Problem Statement    Given a set S of n activities with and start time, S_i and f_i, finish time of an i^th activity. Find the maximum size set of mutually compatible activities.

Compatible Activities
Activities i and j are compatible if the half-open internal [s_i, f_i) and [s_j, f_j) do not overlap, that is, i and j are compatible if s_i ≥ f_j  and s_j ≥  f_i

Dynamic-Programming Algorithm

The finishing time are in a sorted array f[i] and the starting times are in array s[i]. The array m[i] will store the value m_i, where m_i is the size of the largest of mutually compatible activities among activities {1, 2, . . . , i}. Let BINARY-SEARCH(f, s) returns the index of a number i in the sorted array f such that f(i) ≤ s ≤  f[i + 1].

for  i =1  to  n
    do   m[i] = max(m[i-1], 1+ m [BINARY-SEARCH(f, s[i])])
                 We have P(i] = 1 if activity i is in optimal selection, and P[i] = 0
                 otherwise
                 i = n
                while   i > 0
                     do if m[i] = m[i-1]
                             then P[i] = 0
                                        i = i - 1
                             else
                                       i = BINARY-SEARCH (f, s[i])
                                      P[i] = 1

Analysis
The running time of this algorithm is O(n lg n) because of the binary search which takes lg(n) time as opposed to the O(n) running time of the greedy algorithm. This greedy algorithm assumes that the activities already sorted by increasing time.
[http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/activitydyn.htm]

Dynamic-Programming Solution

to the 0-1 Knapsack Problem

Problem Statement    A thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and i^th  item weigh w_i and is worth v_i dollars. What items should thief take?

There are two versions of problem

Fractional knapsack problem    The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of x_i of item i, where 0 ≤ x_i ≤ 1.
0-1 knapsack problem    The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.

Fractional knapsack problem

• Exhibit greedy choice property.
          Þ Greedy algorithm exists.
• Exhibit optimal substructure property.
• Þ

0-1 knapsack problem

• Exhibit No greedy choice property.
          Þ No greedy algorithm exists.
• Exhibit optimal substructure property.
• Only dynamic programming algorithm exists.

 

 

 

Dynamic-Programming Solution to the 0-1 Knapsack Problem

Let i be the highest-numbered item in an optimal solution S for W pounds. Then S` = S - {i} is an optimal solution for W - w_i pounds and the value to the solution S is V_i plus the value of the subproblem.
We can express this fact in the following formula: define c[i, w] to be the solution for items  1,2, . . . , i and maximum weight w. Then

	0	if i = 0 or w = 0
c[i,w]  =	c[i-1, w]	if wi ≥ 0
	max [vi + c[i-1, w-wi], c[i-1, w]}	if i>0 and w ≥  wi

This says that the value of the solution to i items either include i^th item, in which case it is v_i plus a subproblem solution for (i - 1) items and the weight excluding w_i, or does not include i^th item, in which case it is a subproblem's solution for (i - 1) items and the same weight. That is, if the thief picks item i, thief takes v_i value, and thief can choose from items w - w_i, and get c[i - 1, w - w_i] additional value. On other hand, if thief decides not to take item i, thief can choose from item 1,2, . . . , i- 1 upto the weight limit w, and get c[i - 1, w] value. The better of these two choices should be made.
Although the 0-1 knapsack problem, the above formula for c is similar to LCS formula: boundary values are 0, and other values are computed from the input and "earlier" values of c. So the 0-1 knapsack algorithm is like the LCS-length algorithm given in CLR for finding a longest common subsequence of two sequences.
The algorithm takes as input the maximum weight W, the number of items n, and the two sequences v = <v₁, v₂, . . . , v_n> and w = <w₁, w_2, . . . , w_n>. It stores the c[i, j] values in the table, that is, a two dimensional array, c[0 . . n, 0 . . w] whose entries are computed in a row-major order. That is, the first row of c is filled in from left to right, then the second row, and so on. At the end of the computation, c[n, w] contains the maximum value that can be picked into the knapsack.

Dynamic-0-1-knapsack (v, w, n, W)

FOR w = 0 TO W
    DO  c[0, w] = 0
FOR i=1 to n
    DO c[i, 0] = 0
        FOR w=1 TO W
            DO IFf w_i ≤ w
                THEN IF  v_i + c[i-1, w-w_i]
                    THEN c[i, w] = v_i + c[i-1, w-w_i]
                    ELSE c[i, w] = c[i-1, w]
                ELSE
                    c[i, w] = c[i-1, w]

The set of items to take can be deduced from the table, starting at c[n. w] and tracing backwards where the optimal values came from. If c[i, w] = c[i-1, w] item i is not part of the solution, and we are continue tracing with c[i-1, w]. Otherwise item i is part of the solution, and we continue tracing with c[i-1, w-W].

Analysis
This dynamic-0-1-kanpsack algorithm takes θ(nw) times, broken up as follows: θ(nw) times to fill the c-table, which has (n +1).(w +1) entries, each requiring θ(1) time to compute. O(n) time to trace the solution, because the tracing process starts in row n of the table and moves up 1 row at each step.
[http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm]

Longest Common Subsequence)

We have discussed Overlapping Subproblems and Optimal Substructure properties in Set 1 and Set 2 respectively. We also discussed one example problem in Set 3. Let us discuss Longest Common Subsequence (LCS) problem as one more example problem that can be solved using Dynamic Programming.

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.

It is a classic computer science problem, the basis of diff (a file comparison program that outputs the differences between two files), and has applications in bioinformatics.

Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

We strongly recommend that you click here and practice it, before moving on to the solution.

The naive solution for this problem is to generate all subsequences of both given sequences and find the longest matching subsequence. This solution is exponential in term of time complexity. Let us see how this problem possesses both important properties of a Dynamic Programming (DP) Problem.

1) Optimal Substructure: 
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the recursive definition of L(X[0..m-1], Y[0..n-1]).

If last characters of both sequences match (or X[m-1] == Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

If last characters of both sequences do not match (or X[m-1] != Y[n-1]) then
L(X[0..m-1], Y[0..n-1]) = MAX ( L(X[0..m-2], Y[0..n-1]), L(X[0..m-1], Y[0..n-2])

Examples:
1) Consider the input strings “AGGTAB” and “GXTXAYB”. Last characters match for the strings. So length of LCS can be written as:
L(“AGGTAB”, “GXTXAYB”) = 1 + L(“AGGTA”, “GXTXAY”)

2) Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match for the strings. So length of LCS can be written as:
L(“ABCDGH”, “AEDFHR”) = MAX ( L(“ABCDG”, “AEDFHR”), L(“ABCDGH”, “AEDFH”) )

So the LCS problem has optimal substructure property as the main problem can be solved using solutions to subproblems.

2) Overlapping Subproblems:
Following is simple recursive implementation of the LCS problem. The implementation simply follows the recursive structure mentioned above.

• C/C++
• Python

/* A Naive recursive implementation of LCS problem */ #include<bits/stdc++.h>   int max(int a, int b);   /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char *X, char *Y, int m, int n ) {    if (m == 0 || n == 0)      return 0;    if (X[m-1] == Y[n-1])      return 1 + lcs(X, Y, m-1, n-1);    else      return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); }   /* Utility function to get max of 2 integers */ int max(int a, int b) {     return (a > b)? a : b; }   /* Driver program to test above function */ int main() {   char X[] = "AGGTAB";   char Y[] = "GXTXAYB";     int m = strlen(X);   int n = strlen(Y);     printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );     return 0; }

Output:

Length of LCS is 4

Time complexity of the above naive recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0.
Considering the above implementation, following is a partial recursion tree for input strings “AXYT” and “AYZX”

                         lcs("AXYT", "AYZX")
                       /                 \
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /            \                  /               \
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

In the above partial recursion tree, lcs(“AXY”, “AYZ”) is being solved twice. If we draw the complete recursion tree, then we can see that there are many subproblems which are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation. Following is a tabulated implementation for the LCS problem.

• C/C++
• Python

/* Dynamic Programming C/C++ implementation of LCS problem */ #include<bits/stdc++.h>    int max(int a, int b);    /* Returns length of LCS for X[0..m-1], Y[0..n-1] */ int lcs( char *X, char *Y, int m, int n ) {    int L[m+1][n+1];    int i, j;       /* Following steps build L[m+1][n+1] in bottom up fashion. Note       that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */    for (i=0; i<=m; i++)    {      for (j=0; j<=n; j++)      {        if (i == 0 || j == 0)          L[i][j] = 0;           else if (X[i-1] == Y[j-1])          L[i][j] = L[i-1][j-1] + 1;           else          L[i][j] = max(L[i-1][j], L[i][j-1]);      }    }         /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */    return L[m][n]; }    /* Utility function to get max of 2 integers */ int max(int a, int b) {     return (a > b)? a : b; }    /* Driver program to test above function */ int main() {   char X[] = "AGGTAB";   char Y[] = "GXTXAYB";      int m = strlen(X);   int n = strlen(Y);      printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );     return 0; }

Time Complexity of the above implementation is O(mn) which is much better than the worst case time complexity of Naive Recursive implementation.

The above algorithm/code returns only length of LCS. Please see the following post for printing the LCS.
Printing Longest Common Subsequence

[http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/]