Helping!!! data structure problems. Just need to finish the DP.java and pass the test. finishing the three part "bupartition" "buminidistance" "bulcs" using buttom-up like"bucoinChange" thank u.

DP.java

import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.WeakHashMap; import java.util.function.BiFunction; import java.util.function.Function; class DP { /**  * 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 } } /**  * We create a hash table making sure it is called coinChangeMemo.  * Each subproblem is determined by the list of coins and by the desired sum.  * That combination should be the key.  */  static Map,Integer>,Integer> coinChangeMemo = new WeakHashMap(); /**  * We use computeIfAbsent. When we communicate with the hash table, we combine  * all the information into a key and take back apart.  */  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 } }); } /**  * We now manage the memoization table manually. We can choose  * to represent our memoization table as a WeakHashMap or we can  * represent it as an array or whatever data structure gives efficient  * access to the elements. In class we used a WeakHashMap. Here  * we show how to use an array.  */  static int bucoinChange (List coins, int n) throws EmptyListE { /* The possible lists of coins we will encounter are coins, coins.getRest(), * coins.getRest().getRest(), etc. We will refer to these using * array indices 0, 1, 2, ... * The possible sums we will encounter will be a subset of n, n-1, n-2, ... * We will use these directly as indices into the array */ int len = coins.length()+1; int[][] table = new int[len][n+1]; /* * The entries corresponding to the empty list are initialized with 0 (no solutions) * The entries corresponding to sum=0 are initialized with 1 (one solution) * These two initializations must be done in the given order */ for (int i=0; i=0; c--) { int v = coins.get(c).getValue(); for (int i = 1; i/**  * 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) { try { return partition(s.getRest(), sum - s.getFirst()) || partition(s.getRest(), sum); } catch (EmptyListE e) { return sum == 0; } } static Map,Integer>,Boolean> partitionMemo = new WeakHashMap(); static boolean mpartition (List s1, int sum1) { return partitionMemo.computeIfAbsent(new Pair(s1, sum1), p -> { List s = p.getFirst(); int sum = p.getSecond(); try { return mpartition(s.getRest(), sum - s.getFirst()) || mpartition(s.getRest(), sum); } catch (EmptyListE e) { return sum == 0; } }); } static boolean bupartition (List s, int sum) { return false; } final static int GAP = 2; final static int MATCH = 0; final static int MISMATCH = 1; enum BASE { A, T, G, C } static int min (int d1, int d2) { return d1  dna1, List dna2) { try { int current = dna1.getFirst() == dna2.getFirst() ? MATCH : MISMATCH; int d1 = current + minDistance(dna1.getRest(), dna2.getRest()); int d2 = GAP + minDistance(dna1.getRest(), dna2); int d3 = GAP + minDistance(dna1, dna2.getRest()); return min(d1,min(d2,d3)); } catch (EmptyListE e) { if (dna1.isEmpty()) return GAP * dna2.length(); else return GAP * dna1.length(); } } static Map,List>,Integer> minDistanceMvcemo = new WeakHashMap(); static int mminDistance (List dna11, List dna21) { return minDistanceMemo.computeIfAbsent(new Pair(dna11, dna21), p -> { List dna1 = p.getFirst(); List dna2 = p.getSecond(); try { int current = dna1.getFirst() == dna2.getFirst() ? MATCH : MISMATCH; int d1 = current + mminDistance(dna1.getRest(), dna2.getRest()); int d2 = GAP + mminDistance(dna1.getRest(), dna2); int d3 = GAP + mminDistance(dna1, dna2.getRest()); return min(d1,min(d2,d3)); } catch (EmptyListE e) { if (dna1.isEmpty()) return GAP * dna2.length(); else return GAP * dna1.length(); } }); } static int buminDistance (List dna1, List dna2) { return 0; } static List lcs (List cs1, List cs2) { try { if (cs1.getFirst().equals(cs2.getFirst())) { return new Node(cs1.getFirst(), lcs(cs1.getRest(),cs2.getRest())); } else { List r1 = lcs(cs1,cs2.getRest()); List r2 = lcs(cs1.getRest(),cs2); if (r1.length() > r2.length()) return r1; else return r2; } } catch (EmptyListE e) { return new Empty(); } } static Map,List>,List> lcsMemo = new WeakHashMap(); static List mlcs (List cs11, List cs21) { return lcsMemo.computeIfAbsent(new Pair(cs11,cs21), p -> { List cs1 = p.getFirst(); List cs2 = p.getSecond(); try { if (cs1.getFirst().equals(cs2.getFirst())) { return new Node(cs1.getFirst(), mlcs(cs1.getRest(), cs2.getRest())); } else { List r1 = mlcs(cs1, cs2.getRest()); List r2 = mlcs(cs1.getRest(), cs2); if (r1.length() > r2.length()) return r1; else return r2; } } catch (EmptyListE e) { return new Empty(); } }); } static List bulcs (List cs1, List cs2) { } <><>

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 { 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 coinChange correctness and timing @Test public void coinsC() throws EmptyListE { 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, 3)); assertEquals(2, DP.coinChange(coins, 6)); assertEquals(242, DP.coinChange(coins, 100)); assertEquals(1, DP.bucoinChange(coins, 3)); assertEquals(2, DP.bucoinChange(coins, 6)); assertEquals(242, DP.bucoinChange(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 (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)); } @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()); } } }

In this file, I just want to finish three questions "bupartition" "buminidistance" "bulcs" and using the bottom-up like the example "bucoinChange" Coinchange is just a example of other problems.. And you don't need to care about other method. Those classes in picture are support the Dp.java file. And the requirement of those three question are in last three picture. Then just pass the test. Thank u

class Pair private A a; private B b; Pair (A a, Bb)f this.a - a; this.b b; A getFirst t return a; B getSecondt return b; @override public boolean equals(Object o) if (!(o instanceof Pair)) return false; else Pair that (Pair) o return a.equals (that.a) && b.equals(that.b); @override public int hashCode() return a.hashCode() + b.hashCode();h @override public String toString () { return " static List singleton (E e) t return new Node(e, new Empty>)); static List MakeList (Function g, int size) List result = new Empty(); for (int = 0; (g.apply( t: null), result); return result: static List MakeIntList (Random r, int bound, int size) return MakeList( (v) List push (E elem) return new Node(elem, rest: this); abstract E getFirst ) throws EmptyListE; abstract List getRest () throws EmptyListE; abstract E get (int i) throws EmptyListE abstract boolean isEmpty; abstract boolean isSingleton) abstract int length); abstract List add (E elem) abstract Listreverse() abstract List append (List other); abstract List map (Function f); abstract List insertByKey (E elem, FunctionE, Double> key); abstract List sort (FunctionE, Double> key); class Emptyextends List E getFirst throws EmptyListE t throw new EmptyListE); List getRest () throws EmptyListE throw new EmptyListEO; E get (int i) throws EmptyListE throw new EmptyListE); boolean isEmpty) retur boolean isSingleton ) return false; h int length) return 0; h List add (E elem) t return new Node>(elem, rest: this); List reverse()t return this; List append (List other) return other; ) List map (Function f) t return new Empty); n true;h List List 1nsertBykey (E etem, Function,Double> key) sort (FunctionE , Double> key) { return this; return { } new Node (elem, new Empty()); public boolean equals (0bject o) return o instanceof Empty; public int hashCode() return 0; public String toString ) t return "_"; h class Node private E data; private List rest; Node (E data, List rest) t this.data = data; this.rest-rest; E getFirst )t return data; ) List getRest () t return rest;h E get (int i) throws EmptyListE { if (i0) return data; else return rest.get (i-1); boolean isEmpty () return false; ) boolean isSingleton ()t return rest.isEmpty(); h int length) t return 1+ rest.length); List add (E elem) return new Node>(data, rest.add(elem)); List reverse )f return rest.reverse().add (data); List append (List other) T return new Node (data, rest.append(other)); List map (Function f) return new Node>(f.apply(data), rest.map(f)); List insertByKey (E elem, Function key) if (key.apply (elem) (data, rest.insertByKey (elem, key)); | List sort (FunctionE,Double> key) { return rest. sort (key), insertByKey(data, key); } public boolean equals (0bject o) if (! (o instanceof Node)) return false; else t de that(Node) o return data.equals (that.data) && rest.equals(that.rest); No public int hashCode() return data.hashCode() + rest.hashCode(); h public String toString return data "," rest; h pub lic cLass Coln1 private int value; Coin (int value) this.value value; int getValue ) return value; h @override public boolean equals(Object o) f if (!(o instanceof Coin)) return false; else t Coin that-(Coin) o; return value = that . value; @Override public int hashCode() return value; @override public String toStringtreturn "@" +value;h 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. class Pair private A a; private B b; Pair (A a, Bb)f this.a - a; this.b b; A getFirst t return a; B getSecondt return b; @override public boolean equals(Object o) if (!(o instanceof Pair)) return false; else Pair that (Pair) o return a.equals (that.a) && b.equals(that.b); @override public int hashCode() return a.hashCode() + b.hashCode();h @override public String toString () { return " static List singleton (E e) t return new Node(e, new Empty>)); static List MakeList (Function g, int size) List result = new Empty(); for (int = 0; (g.apply( t: null), result); return result: static List MakeIntList (Random r, int bound, int size) return MakeList( (v) List push (E elem) return new Node(elem, rest: this); abstract E getFirst ) throws EmptyListE; abstract List getRest () throws EmptyListE; abstract E get (int i) throws EmptyListE abstract boolean isEmpty; abstract boolean isSingleton) abstract int length); abstract List add (E elem) abstract Listreverse() abstract List append (List other); abstract List map (Function f); abstract List insertByKey (E elem, FunctionE, Double> key); abstract List sort (FunctionE, Double> key); class Emptyextends List E getFirst throws EmptyListE t throw new EmptyListE); List getRest () throws EmptyListE throw new EmptyListEO; E get (int i) throws EmptyListE throw new EmptyListE); boolean isEmpty) retur boolean isSingleton ) return false; h int length) return 0; h List add (E elem) t return new Node>(elem, rest: this); List reverse()t return this; List append (List other) return other; ) List map (Function f) t return new Empty); n true;h List List 1nsertBykey (E etem, Function,Double> key) sort (FunctionE , Double> key) { return this; return { } new Node (elem, new Empty()); public boolean equals (0bject o) return o instanceof Empty; public int hashCode() return 0; public String toString ) t return "_"; h class Node private E data; private List rest; Node (E data, List rest) t this.data = data; this.rest-rest; E getFirst )t return data; ) List getRest () t return rest;h E get (int i) throws EmptyListE { if (i0) return data; else return rest.get (i-1); boolean isEmpty () return false; ) boolean isSingleton ()t return rest.isEmpty(); h int length) t return 1+ rest.length); List add (E elem) return new Node>(data, rest.add(elem)); List reverse )f return rest.reverse().add (data); List append (List other) T return new Node (data, rest.append(other)); List map (Function f) return new Node>(f.apply(data), rest.map(f)); List insertByKey (E elem, Function key) if (key.apply (elem) (data, rest.insertByKey (elem, key)); | List sort (FunctionE,Double> key) { return rest. sort (key), insertByKey(data, key); } public boolean equals (0bject o) if (! (o instanceof Node)) return false; else t de that(Node) o return data.equals (that.data) && rest.equals(that.rest); No public int hashCode() return data.hashCode() + rest.hashCode(); h public String toString return data "," rest; h pub lic cLass Coln1 private int value; Coin (int value) this.value value; int getValue ) return value; h @override public boolean equals(Object o) f if (!(o instanceof Coin)) return false; else t Coin that-(Coin) o; return value = that . value; @Override public int hashCode() return value; @override public String toStringtreturn "@" +value;h 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