DP classes

import java.util.HashMap; import java.util.Map; import java.util.WeakHashMap; import java.util.function.Function; class DP { /**  * Trivial example to show the pattern: fib  * First write the normal recursive solution  */  static long fib (int n) { if (n fib(n-1) + fib (n- 2); } /**  * Create a hash table: please call it fibMemo as we will refer  * to it from the test suite.  */  static Map fibMemo = new WeakHashMap(); /**  * Use the method computeIfAbsent passing the naive recursive  * computation as an argument. Do not forget to rename the  * recursive calls to refer to the memoized version.  *  * There will typically be small additional tweaks to do. In  * this case, I had to explicitly cast from int to long  * in the return clause for the base case.  */  static long mfib (int n1) { return fibMemo.computeIfAbsent(n1, n -> { if (n mfib(n - 1) + mfib(n - 2); }); } /**  * For fun... Compute fib using the golden ratio.  */  static long ffib (int n) { } // ----------------------------------------------------------------------------- // Coin changing... // ----------------------------------------------------------------------------- /**  * Given a list of possible coins that must include a penny,  * and a number of pennies 'n', in how many ways can we use the  * coins to make change for 'n'.  */  static int coinChange (List coins, int n) { try { if (n coinChange(coins.getRest(), n) + coinChange(coins,n - coins.getFirst().getValue()); } catch (EmptyListE e) { return 0; // no way to make change } } /**  * Again we create a hash table making sure it is called  * coinChangeMemo. But here we have to think a bit. Each  * subproblem is determined by the list of coins and by the  * desired sum. That combination should be the key used  * in hashing.  */  static Map,Integer>,Integer> coinChangeMemo = new WeakHashMap(); /**  * We again want to use computeIfAbsent. When we communicate with  * the hash table, we combine all the information into a key and  * take back apart when we extract from the hash table.  */  static int mcoinChange (List coins1, int n1) { return coinChangeMemo.computeIfAbsent(new Pair(coins1,n1), p -> { List coins = p.getFirst(); int n = p.getSecond(); try { if (n mcoinChange(coins.getRest(), n) + mcoinChange(coins, n - coins.getFirst().getValue()); } catch (EmptyListE e) { return 0; // no way to make change } }); } // ----------------------------------------------------------------------------- // Partition ... // ----------------------------------------------------------------------------- /**  * Partition: take a list, a desired sum 's', and return  * T/F depending on whether it is possible to find a  * subsequence of the list whose sum is exactly 's'  */  static boolean partition (List s, int sum) { Node ns; return false; } static Object partitionMemo = null; static boolean mpartition (List s1, int sum1) { return false; } // ----------------------------------------------------------------------------- // Min distance ... // ----------------------------------------------------------------------------- final static int GAP = 2; final static int MATCH = 0; final static int MISMATCH = 1; enum BASE { A, T, G, C } static int minDistance (List dna1, List dna2) { return 0; } static Object minDistanceMemo = null; static int mminDistance (List dna11, List dna21) { return 0; } // ----------------------------------------------------------------------------- // Longest common subsequence ... // ----------------------------------------------------------------------------- static List lcs (List cs1, List cs2) { return null; } static Object lcsMemo = null; static List mlcs (List cs11, List cs21) { return null; } } 

test.file

import org.junit.Test; import java.util.Random; import java.util.function.BiFunction; import java.util.function.Function; import static org.junit.Assert.*; public class DPTest { // Timers static  long time1 (Function f, A a) { long start = System.nanoTime(); f.apply(a); long end = System.nanoTime(); return (end-start)/1000000; } static  long time2 (BiFunction f, A a, B b) { long start = System.nanoTime(); f.apply(a,b); long end = System.nanoTime(); return (end-start)/1000000; } // Testing fib correctness and timing @Test public void fib () { assertEquals(DP.fib(15), DP.mfib(15)); long slow, fast; slow = time1(DP::fib, 30); fast = time1(DP::mfib, 30); assertTrue(slow > fast); slow = time1(DP::fib, 40); fast = time1(DP::mfib, 40); assertTrue(slow > fast); } @Test(timeout=5) public void fibT () { DP.fibMemo.clear(); DP.mfib(100); } @Test public void ffib () { DP.fibMemo.clear(); long n1 = DP.mfib(50); long n2 = DP.ffib(50); assertEquals(n1, n2); } @Test(timeout=20) public void ffibT () { DP.fibMemo.clear(); DP.mfib(1000); DP.ffib(1000); } // Testing coinChange correctness and timing @Test public void coinsC () { Coin quarter = new Coin(25); Coin dime = new Coin(10); Coin nickel = new Coin(5); Coin penny = new Coin(1); List coins = new Node(quarter, new Node(dime, new Node(nickel, new Node(penny, new Empty())))); assertEquals(1, DP.coinChange(coins, 4)); assertEquals(2, DP.coinChange(coins, 6)); assertEquals(242, DP.coinChange(coins,100)); } @Test(timeout=500) public void coinsT1 () { List coins = new Node(new Coin(3), new Node(new Coin(2), new Node(new Coin(1), new Empty()))); DP.coinChangeMemo.clear(); DP.mcoinChange(coins,1000); } // Testing partition correctness and timing @Test public void partitionCorrectness () { List ns = new Node(5, new Node(3, new Node(7, new Node(1, new Empty())))); assertFalse(DP.partition(ns, 2)); assertTrue(DP.partition(ns, 8)); assertTrue(DP.partition(ns, 6)); } @Test public void partitionTiming () { Random r = new Random(1); List s = List.MakeIntList(r, 100, 1000); DP.partitionMemo.clear(); long t = time2(DP::mpartition,s,50000); assertTrue (t  dna1 = new Node(DP.BASE.A, new Node(DP.BASE.C, new Empty())); List dna2 = new Node(DP.BASE.A, new Node(DP.BASE.G, new Empty())); assertEquals(1, DP.minDistance(dna1,dna2)); } @Test public void minDistance2 () { Random r = new Random(1); Function g = v -> DP.BASE.class.getEnumConstants()[r.nextInt(4)]; List dna1 = List.MakeList(g, 521); List dna2 = List.MakeList(g, 450); assertEquals(337, DP.mminDistance(dna1,dna2)); } // longest common subsequence @Test public void lcs () { List cs1 = new Node('A', new Node('B', new Node('C', new Node('B', new Node('D', new Node('A', new Node('B', new Empty()))))))); List cs2 = new Node('B', new Node('D', new Node('C', new Node('A', new Node('B', new Node('A', new Empty())))))); List c = new Node('B', new Node('D', new Node('A', new Node('B', new Empty())))); assertEquals(c, DP.lcs(cs1,cs2)); } @Test public void lcs2 () { Random r = new Random(1); Function g = v -> Character.forDigit(r.nextInt(256),10); List cs1 = List.MakeList(g, 310); List cs2 = List.MakeList(g, 250); assertEquals(240, DP.mlcs(cs1,cs2).length()); } } 

Requirement

Thank you very much.

2 Fibonacci You are given the usual recursive definition of fib and its memoized version. There is also a direct definition: TL (1- V5 Implement this definition and test it for both correctness and speed. For really large values of n, how does this compare to the memoized version? Do you think this implementation is (1)? 3 Coins You are given the solution to this problem. Make sure you understand it. Write several additional test cases. 4 Partition You are given a list of numbers and a target sum. Your job is to determine whether there is a subsequence of the list that sums to the given target. A subsequence of a list contains some of the list of the elements in the same order as they appear in the original list. So for example, if the given list is: then [1,8] is a subsequence but [8,1] is not 5 Minimum Distance You are given two lists of DNA bases and you need to determine how "close" they are to each other. The definition of "close" is determined by the following notion of cost calculated as you traverse the two lists comparing elements if the two elements under consideration match the cost is 0; if the two elements do not match, then you have three options you could add a cost of 1 for a mismatch and continue calculating the cost with the remainders of the two lists; you could shift one of the lists by one position but paying a cost of 2 For example, if the two lists were: [T,A,T,A,C] [A,T,A,C] When comparing the first two elements, you could decide there is a mismatch paying a cost of 1, then you pay again for the next two elements, and again for the ones after that. Or you could pay a cost of 2 initially shifting the bottom list to make a perfect match. Your goal is to calculate the minimum cost. 6 Longest Common Subsequence In this last problem, you are given two lists of characters and your job is find the long common subsequence For example, if the two lists are: [a,b,c,d,a,a,a,b,a,c] 6 Longest Common Subsequence In this last problem, you are given two lists of characters and your job is find the long common subsequence. For example, if the two lists are [a,b,c,d,a,a,a,b,a,c] [a,a,a,a,b,d,d,a,c] There are several common subsequences like [b,cl, [b], [a,a,a,a,a]. Your job is to compute the longest such subsequence. 2 Fibonacci You are given the usual recursive definition of fib and its memoized version. There is also a direct definition: TL (1- V5 Implement this definition and test it for both correctness and speed. For really large values of n, how does this compare to the memoized version? Do you think this implementation is (1)? 3 Coins You are given the solution to this problem. Make sure you understand it. Write several additional test cases. 4 Partition You are given a list of numbers and a target sum. Your job is to determine whether there is a subsequence of the list that sums to the given target. A subsequence of a list contains some of the list of the elements in the same order as they appear in the original list. So for example, if the given list is: then [1,8] is a subsequence but [8,1] is not 5 Minimum Distance You are given two lists of DNA bases and you need to determine how "close" they are to each other. The definition of "close" is determined by the following notion of cost calculated as you traverse the two lists comparing elements if the two elements under consideration match the cost is 0; if the two elements do not match, then you have three options you could add a cost of 1 for a mismatch and continue calculating the cost with the remainders of the two lists; you could shift one of the lists by one position but paying a cost of 2 For example, if the two lists were: [T,A,T,A,C] [A,T,A,C] When comparing the first two elements, you could decide there is a mismatch paying a cost of 1, then you pay again for the next two elements, and again for the ones after that. Or you could pay a cost of 2 initially shifting the bottom list to make a perfect match. Your goal is to calculate the minimum cost. 6 Longest Common Subsequence In this last problem, you are given two lists of characters and your job is find the long common subsequence For example, if the two lists are: [a,b,c,d,a,a,a,b,a,c] 6 Longest Common Subsequence In this last problem, you are given two lists of characters and your job is find the long common subsequence. For example, if the two lists are [a,b,c,d,a,a,a,b,a,c] [a,a,a,a,b,d,d,a,c] There are several common subsequences like [b,cl, [b], [a,a,a,a,a]. Your job is to compute the longest such subsequence