Written in Java

Consider the Subset Sum Problem, formally defined as: Subset Sum (SS): INPUT: a list S[O...n-1) of n positive integers, and a target integer t2 0. OUTPUT: TRUE and a set of indices AS {0...n-1} such that LieAS[i] = t if such an A exists, or FALSE otherwise. This problem can be solved by brute force or with dynamic programming. The following clever algorithm has also been proposed to solve SS: 1. Split the indices {0...n-1} into two sets of nearly equal size, L = {0... [n[2]} and H= {[n/2] +1...n-1}. 2. Compute a table T of all subsets of L that yield a subset of S of weight not exceeding t (that is, a table containing all I SL such that Liel S[i] = t). If equality holds for some 1, i.e. Liel S[i] = t, then return TRUE and I, and stop. 3. Compute a table W of all subsets of H that yield a subset of S of weight not exceeding t (that is, a table containing all J S H such that Ejes S[j] = t). If equality holds for some J, i.e. Ejej S[j] = t, then return TRUE and J, and stop. 4. Sort table W in ascending order of weights. 5. For each entry I in table T, find the subset J S H that yields the maximum weight not exceeding t when joined to I, i.e. (Eier S[i])+(jej S[jl) st. If equality holds for some I and some ), i.e. (Eiei S[i]) + (jej S[j]) = t, then return TRUE and IUJ, and stop. 6. If no subsets I and J yield equality, return FALSE and the empty set, and stop. The overall goal of this programming assignment is to test and compare these three proposed solutions. 3.1 BRUTE FORCE (4 points): Design and implement a brute force solution for this problem. Run it according to the testing procedure described below in section 3.4. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.2 DYNAMIC PROGRAMMING (DP) (6 points): Design and implement a DP solution for this problem. Run it according to the testing procedure described below. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.3 CLEVER ALGORITHM (8 points): Design and implement a solution for this problem based on the allegedly) clever algorithm. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.4 TESTING (4 points): Design and implement a method Driver that, given two integers n and r and a Boolean value v as input, creates a sequence of n random elements sampled from range 1 to r, then tests each of the above algorithms on S for a target t chosen as, for v = TRUE, the sum of a random subset of S (so that a solution is guaranteed to exist), and for v = FALSE, a random value larger than the sum of all values on S (so that there is no solution). The Driver method must measure the time in milliseconds) each of the three algorithms takes to complete, and record how much table space each algorithm needs for that particular combination of n and t. When the tests are done, Driver must also print the values of n and r, the generated sequence Sand, for each of the three algorithms, the subsequence of elements from Seach algorithm found that sums up to t (or an indication that none such subsequence exists), and the running time and table space requirements of that algorithm for that S. Run Driver for each of the following combinations: r= 1,000, v = TRUE or FALSE (test both), and n=5,6,7.... up to the largest value of n each algorithm can test so that it takes no more than 5 minutes for that n; . r= 1,000,000, v = TRUE or FALSE (test both), and n= 5,6,7,... up to the largest value of neach algorithm can test so that it takes no more than 5 minutes for that n. Notice that the largest value of n may be different for each algorithm. If a certain combi- nation of n, r, and v is infeasible for some algorithm, skip that algorithm but test the other one(s). Consider the Subset Sum Problem, formally defined as: Subset Sum (SS): INPUT: a list S[O...n-1) of n positive integers, and a target integer t2 0. OUTPUT: TRUE and a set of indices AS {0...n-1} such that LieAS[i] = t if such an A exists, or FALSE otherwise. This problem can be solved by brute force or with dynamic programming. The following clever algorithm has also been proposed to solve SS: 1. Split the indices {0...n-1} into two sets of nearly equal size, L = {0... [n[2]} and H= {[n/2] +1...n-1}. 2. Compute a table T of all subsets of L that yield a subset of S of weight not exceeding t (that is, a table containing all I SL such that Liel S[i] = t). If equality holds for some 1, i.e. Liel S[i] = t, then return TRUE and I, and stop. 3. Compute a table W of all subsets of H that yield a subset of S of weight not exceeding t (that is, a table containing all J S H such that Ejes S[j] = t). If equality holds for some J, i.e. Ejej S[j] = t, then return TRUE and J, and stop. 4. Sort table W in ascending order of weights. 5. For each entry I in table T, find the subset J S H that yields the maximum weight not exceeding t when joined to I, i.e. (Eier S[i])+(jej S[jl) st. If equality holds for some I and some ), i.e. (Eiei S[i]) + (jej S[j]) = t, then return TRUE and IUJ, and stop. 6. If no subsets I and J yield equality, return FALSE and the empty set, and stop. The overall goal of this programming assignment is to test and compare these three proposed solutions. 3.1 BRUTE FORCE (4 points): Design and implement a brute force solution for this problem. Run it according to the testing procedure described below in section 3.4. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.2 DYNAMIC PROGRAMMING (DP) (6 points): Design and implement a DP solution for this problem. Run it according to the testing procedure described below. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.3 CLEVER ALGORITHM (8 points): Design and implement a solution for this problem based on the allegedly) clever algorithm. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.4 TESTING (4 points): Design and implement a method Driver that, given two integers n and r and a Boolean value v as input, creates a sequence of n random elements sampled from range 1 to r, then tests each of the above algorithms on S for a target t chosen as, for v = TRUE, the sum of a random subset of S (so that a solution is guaranteed to exist), and for v = FALSE, a random value larger than the sum of all values on S (so that there is no solution). The Driver method must measure the time in milliseconds) each of the three algorithms takes to complete, and record how much table space each algorithm needs for that particular combination of n and t. When the tests are done, Driver must also print the values of n and r, the generated sequence Sand, for each of the three algorithms, the subsequence of elements from Seach algorithm found that sums up to t (or an indication that none such subsequence exists), and the running time and table space requirements of that algorithm for that S. Run Driver for each of the following combinations: r= 1,000, v = TRUE or FALSE (test both), and n=5,6,7.... up to the largest value of n each algorithm can test so that it takes no more than 5 minutes for that n; . r= 1,000,000, v = TRUE or FALSE (test both), and n= 5,6,7,... up to the largest value of neach algorithm can test so that it takes no more than 5 minutes for that n. Notice that the largest value of n may be different for each algorithm. If a certain combi- nation of n, r, and v is infeasible for some algorithm, skip that algorithm but test the other one(s)