You must follow these instructions for in preparing your solution: 1. describe u

ID: 3804501 • Letter: Y

Question

You must follow these instructions for in preparing your solution:

1. describe using English the algorithm you design,

2. write pseudocode in the style of the CLRS text for your algorithm,

3. define tight asymptotic upper bounds for your algorithm’s running time.

Let us define “nearly equal” to mean equal to as many decimal places as possible given some numerical processing and computation time constraints. For example, and 355/113 are nearly equal, differing by -2.66764 E-07.

The numbers {1, 2, …, 50} are to be partitioned into two sets whose sum is most nearly equal. Find the most nearly equal partition you can, using the least amount of computer processor time but no more than 10 seconds of computer processor time.

You must execute your algorithm, producing both a numerical solution and a record of computer processor time used. You must submit your program code for this problem.

1. Be sure to produce a test driver program in a separate file/class from your algorithm program a. (as demonstrated by examples posted for TestInsertionSort.java and InsertionSort.java)

2. Be sure to follow the delivery instructions in the syllabus including: a. try to limit wrapped lines and prevent truncated lines in your printed output

Explanation / Answer

It's an NP complete "partition" problem, so finding an optimal solution is going to be a real tough job. Since, we are looking for "nearly equal" sum, greedy algorithm is pretty good approximation which will be much simpler and is almost perfect.

1.
a. This greedy algorithm works by iterating through the numbers in non-increasing order and assigning each value to the subset that has smaller sum.
b. It takes O(nlogn) time since, we have to sort the numbers and iterate over them only once assigning each one of them to a subset.

2. FIND_PARTITIONS(S)
     S' SORT_DESC(S)
     A
     B
   for N in S'
        if sum(A) < sum(B)
       A A U {N}
        else
       B B U {N}
   return (A, B)

3. The algorithm takes O(nlogn) time because it sorts the input set in O(nlong) time, and then traverses it once assigning each of the value either to subset A or to subset B, in O(n) time. So, overall time complexity is O(nlogn)

Code

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class Partition {

   public void partition(List<Integer> S, List<Integer> A, List<Integer> B) {

       MergeSortDesc.mergeSortDesc(S, 0, S.size()-1);
       int sumA = 0;
       int sumB = 0;

       for (Integer N : S) {
           if (sumA < sumB) {
               A.add(N);
               sumA += N;
           }
           else {
               B.add(N);
               sumB += N;
           }
       }

       System.out.println("Set A = {" + A + "}");
       System.out.println("Set B = {" + B + "}");
       System.out.println("Minimal Difference is = "+ (sumA-sumB));
   }

   public static void main(String args[]) {
       List<Integer> S = new ArrayList<Integer>();
       List<Integer> A = new ArrayList<Integer>();
       List<Integer> B = new ArrayList<Integer>();
       Random random = new Random();
       for (int i=0; i<10; i++) {
           S.add(random.nextInt(100));
       }
       System.out.println(S);
       new Partition().partition(S, A, B);
   }
}

class MergeSortDesc {

   public static void mergeSortDesc(List<Integer> array, int low, int high) {
       if (low < high) {
           int mid = (low+high)/2;
           mergeSortDesc(array, low, mid);
           mergeSortDesc(array, mid+1, high);
           merge(array, low, mid, high);
       }
   }

   public static void merge(List<Integer> array, int low, int mid, int high) {
       int[] temp = new int[high-low+1];
       int tempIndex = 0;

       int start1 = low;
       int end1 = mid;

       int start2 = mid+1;
       int end2 = high;

       while ((start1 <= end1) && (start2 <= end2)) {
           if (array.get(start1) > array.get(start2)) {
               temp[tempIndex++] = array.get(start1);
               start1++;
           }

           if (array.get(start2) > array.get(start1)) {
               temp[tempIndex++] = array.get(start2);
               start2++;
           }
       }

       while (start1 <= end1) {
           temp[tempIndex++] = array.get(start1);
           start1++;
       }
       while (start2 <= end2) {
           temp[tempIndex++] = array.get(start2);
           start2++;
       }

       for (int i=0; i<temp.length; i++) {
           array.set(i + low, temp[i]);
       }
   }

}

Navigate

You must follow these instructions for Problems: 1. describe the algorithm you d

You must have a main function, a parse function, a displayValues function, a pus

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You must follow these instructions for in preparing your solution: 1. describe u

Question

Explanation / Answer

Related Questions

Navigate