Dynamic programming

Summary

Dynamic programming as an algorithm design method comprises several optimization levels:

• Eliminate redundand work on identical subproblems by using a table to store results (memoization).
• Eliminate recursivity - find out the order in which the elements of the table have to be computed (dynamic programming)
• Reduce memory complexity if possible

Examples presented in Class

Example with complete code: Binomial coefficients

By its definition, C(n,k)=n! / ((n-k)!*k!)

This definition formula is not used for computation because even for small values of n, the values of n factorial n! get really large.

Instead, C(n,k) can be computed by following formula:

C(n,k)=C(n-1, k-1)+C(n-1, k)

There are several implementations possible for a binomial coefficient solver. The binomial coefficient solver interface implemented by all solvers is IBinomialCoef.java. In this way, the main program can use and experiment with different implementations of the binomial coefficient solver. Such a program is given in ProgramBinomialCoef.java

The implementations of IBinomialCoeff are the following:

1. An inefficient recursive solution is given in BinomialCoefRec.java. When trying to run the program ProgramBinomialCoef, notice that for n>35 this recursive version has a very long running time, you may remove it from the program.
2. A recursive solution based on memoization avoid computing the same C(x,y), by using a table to store the results is given in BinomialCoefMemoization.java
3. An iterative dynamic programming solution is possible when managing to figure out the order in which the table has to be filled out. BinomialCoefDynProg.java
4. A memory efficient dynamic programming version is possible because we notice that every iteration step works with only 2 rows of the table. The amount of memory required by the program is reduced by using 2 buffers for these 2 rows only and reusing the buffers. BinomialCoefDynProgMemEff.java
5. You could optimize even more the memory usage allocating the rows of size k intead of size n.

Download code: you may download code as a single archive of source code binomial_src.zip .

Implementation exercises

The Integer Exact Knapsack

See Lecture, slides 24-35

See also in [Manber - 5.10]

Given an integer K and n items of different sizes such that the i-th item has an integer size weight[i], determine if there is a subset of the items whose weights sum to exactly K, or determine that no such subset exist.

Example1: Consider n=8, weights={8,4,1,2,3,1,4,1} and K=16. This problem has a solution (a subset summing the total weight K=16 is {8,4,1,3}).

Example2: Consider n=3, weights={5,6,8} and K=7. This problem has no solution.

The Integer Exact Knapsack problem has 2 versions:

• The Simple version, requesting to find out only if there is a solution. Such a knapsack solver implements the interface IKnapsackSimple.java
• The Complete version, requesting to find out the list of selected items if there is a solution. Such a knapsack solver implements the interface IKnapsackComplete.java

You are given the inefficient recursive implementation for KnapsackSimple_Recursive.java and KnapsackComplete_Recursive.java.

You are also given two test programs, one using a IKnapsackSimple solver respectively a IKnapsackComplete solver. These two programs are ProgramKnapsackSimple.java respectively ProgramKnapsackComplete.java. The test programs run the integer exact knapsack algorithm on 3 sets of randomly generated weights: the first one, in demo mode, for a short set of n=8, the second one for a medium set of n=1000 and the third for a long set of n=10000. While the simple recursive solutions work well for the short set, they will get stack overflow errors for the long set. A dynamic programming solution using a big table will most likely get out of memory errors for very long sets.

Optimize the implementations of the integer exact knapsack solvers such that they can handle long sets of weights. There are following possibilities:

For the Simple Knapsack:

• iterative dynamic programming solution: write your implementation for KnapsackSimple_DynProgr
• memory efficient dynamic programming solution: write your implementation for KnapsackSimple_DynProgMemEff

For the Complete Knapsack:

• iterative dynamic programming solution: write your implementation for KnapsackComplete_DynProg
• (*)memory efficient dynamic programming solution: you can try to elliminate the big table used in the dynamic programing version, but you will need to store all partial results. In the worst case (the solution comprises all n items from the initial set), memory complexity is still the same as when using the big table, but in the average case, when the selected items are fewer, there will be some improvement. Write implementation KnapsackComplete_NoTable

Download code: you may download the six files discussed above (IKnapsackSimple, KnapsackSimple_Recursive, ProgramKnapsackSimple, IKnapsackComplete, KnapsackComplete_Recursive, ProgramKnapsackComplete) as a single archive of source code ks_src.zip .

Longest common subsequence

See Lecture, slides 36-48

See also [CLRS - chap 15.4]

Given 2 sequences, X ={x1, ..., xm} and Y ={y1, ..., yn}. Find a subsequence common to both whose length is longest. A subsequence does not have to be formed by consecutive elements, but the elements have to be in order.

Example: The Length of the LCS of strings HORSEBACK and SNOWFLAKE is 3. Two such LCS are OAK or SAK.

The LCS problem has 2 versions:

• The Simple version, requesting to find out only the length of the LCS. Such a LCS solver implements the interface ILCS_Simple.java
• The Complete version, requesting to find out the contents of the LCS as well as its length. Such a LCS solver implements the interface ILCS_Complete.java

You are given the inefficient recursive implementations for LCS_Simple_Recursive.java and LCS_Complete_Recursive.java.

You are also given two test programs, one using a ILCS_Simple solver respectively a ILCS_Complete solver. These two programs are ProgramLCS_Simple.java respectively ProgramLCS_Complete.java. The test programs run the LCS algorithm on 3 pairs of strings: a pair of short strings (about 10 characters), a pair of medium strings (about 20 characters) and a pair of long strings (some hundreds characters). While the simple recursive solutions work well for the short strings, you have to wait a little for getting the result in the case of the medium strings, and most probably you will run out of time waiting for the result of the long strings; and you haven't even tried some very long strings as of thousands of characters.

Optimize the implementations of the LCS solvers such that they can handle long strings. There are following possibilities:

For the Simple LCS:

• iterative dynamic programming solution: write your implementation for LCS_Simple_DynProgr
• memory efficient dynamic programming solution: write your implementation for LCS_Simple_DynProgMemEff

For the Complete LCS:

• iterative dynamic programming solution: write your implementation for LCS_Complete_DynProg
• (*)memory efficient dynamic programming solution: you can try to elliminate the big table used in the dynamic programing version, but you will need to store all partial results. In the worst case (the two strings are identic) the memory complexity is still the same as when using the big table, but in the average case, when the common subsequence of the strings is shorter, there will be some improvement. Write your implementation for LCS_Complete_NoTable

Download code: you may download the six files discussed above (ILCS_Simple, LCS_Simple_Recursive, ProgramLCS_Simple, ILCS_Complete, LCS_Complete_Recursive, ProgramLCS_Complete) as a single archive of source code LCS_src.zip .

Additional Exercises

Rod Cutting

Given a rod of length n inches and an array of prices that includes prices of selling all pieces of size smaller than n. Determine the maximum profit obtainable by cutting up the rod and selling the pieces.

Example: if length of rod is n=4 and prices={1, 5, 8, 9, 10, 17, 17, 20, 24, 30} the maximum profit is 10 (can be obtained cutting 2 pieces of length 2).

Example: if length of rod is n=5 and prices={1, 5, 8, 9, 10, 17, 17, 20, 24, 30} the maximum profit is 13 (can be obtained cutting a piece of length 2 and a piece of length 3).

There is no correlation between lebgths of pieces and their price (the values in array prices are not necessary in increasing order).

Another example: if the length of the rod is n=5 and prices={5, 7, 2, 1, 1, 2, 2, 2, 2, 2} the max profit is 25 (cut 5 pieces of length 1 each).

The problem has two requirements versions:

The Simple result version requires to find out only the value of the maximum profit.

The Complete result version requires to find also the sequence of cuts that lead to the maximum profit.

Here you have implementations as recursive algorithms:

Simple result: RodCuttingSimple.java

Complete result: RodCuttingComplete

Apply techniques of Dynamic Programming in order to reduce the time complexity:

• use memoization
• eliminate recursivity

The Minimum Edit Distance

Given two strings X and Y of size m and n, and a set of operations replace, insert and delete. Find the minimum number of operations required to convert one string into another.

Example: First string is: INTENTION Second string is: EXECUTION

In order to transform string X into string Y, the minimum number of operations is 5 operations:
Replace I by E
Replace N by X
Delete T
Replace N by C
Insert U

The problem has two requirements versions:

The Simple result version requires to find out only the number of operations.

The Complete result version requires to find also the sequence of operations.

Here you have implementations as recursive algorithms:

Simple result: MinimumEditDistance.java

Complete result: MinEditDistanceOperations.java

Apply techniques of Dynamic Programming in order to reduce their time complexity:

• use memoization
• eliminate recursivity

Count Structurally Unique Binary Search Trees

The input is N, the number of nodes in the tree .

The output is the count of all the uniquely structured binary search trees that can be built from N different values.

Hints:

The number of structurally different Binary Search Trees is not equal with the number of permutations of N numbers. It is possible that two different permutations (representing the order of insertions in the BST) lead to the same structure of a BST. For example, if N=3, and the 3 different values are 4,7,9, the insertion orders (7,4,9) and (7,9,4) generate the same structure of BST.

Design by induction hints:

• Base case: if N=0 count(0)=0; if N=1 count(1)=1;
• Inductive step: if we know count(k), for all sizes k smaller than N, then how can we deduce count(N) based on count(k)?

Implement a recursive version based on the design by induction hints.

Apply dynamic programming techniques and eliminate recursivity.

Cost of Optimal Binary Search Tree

Read the input from a textfile with the following format: The first line contains N, the number of nodes in the tree The next N lines contain the values of the Keys, in increasing order The next N lines contain the values of the keys frequencies

The output is the value of the cost of the Optimal Binary Search tree that can be built

Hints: Intuitively keys with bigger frequencie must be at lower levels in the tree (near the root).

Design by induction hints: consider the parametrized problem Cost(i,j) which computes the optimal cost of a BST with keys from i to j.

• Base case: if (i>j) then no nodes, cost=0; if (i==j) then one node only, cost=freq[i].
• inductive step: To determine Cost(i, j) we must examine all trees that have as root one of the nodes r between i and j and that have optimal BSTs as subtrees. The left subtree is an optimal BST with cost equal to Cost(i, r-1) and the right subtree is an optimal BST with Cost(r+1, j). When composing the Cost(i,j) from the minimum cost oall f pairs of possible subtrees we must add the sum of frequencies from i to j because the level of all subproblems roots and all their descendant nodes will become bigger with 1 level.

Implement a recursive version based on the design by induction hints.

Apply dynamic programming techniques and eliminate recursivity.

The Maximum Consecutive Subsequence (*)

Given a sequence X = (x[1], x[2],.., x[n]) of (not necessarily positive) real numbers, find a subsequence x[i]; x[i+1]; ...; x[j] of consecutive elements such that the sum of the numbers in it is maximum over all subsequences of consecutive elements

Examples: in the sequence (2, -3, 1.5, -1, 3, -2, -3, 3) the Maximum Consecutive Subsequence (MCS) is (1.5; -1; 3) having the sum 3.5. If all the numbers in the sequence are negative, then the MCS is empty.

Hints:

The base case: if n=1: if the number is nonnegative, the MCS is that single number; otherwise the MCS is empty.

Try to construct an induction hypothesis: We know how to find the MCS for sequences of sizes smaller than n. How can we use this knowledge to find MCS for sequences of size n ? For a sequence x[1] ... x[n] its MCS is either the MCS of the sequence x[1]...x[n-1], or a new MCS formed by the maximum suffix subsequence of X[n-1] appended with element x[n]. We define the maximum suffix subsequence as the maximum subsequence that ends in x[n-1].