public class MaxSumMain { public static void main (String[] args) { int[] toTest

Question

public class MaxSumMain
{

public static void main (String[] args)
{

int[] toTest = new int[] { 1, -1, 2, -1, -1, -1, -1, -1, -1 };

System.out.print("[");

for (int i : toTest)
System.out.print(i + " ");

System.out.println ("] ");

System.out.println("maxSubSum1: " + maxSubSum1(toTest));

System.out.println("maxSubSum2: " + maxSubSum2(toTest));

System.out.println("maxSubSum3: " + maxSubSum3(toTest));

}

public static int maxSubSum1 (int[] arr)
{

int size = arr.length;

int maxSum = -1;

for (int i = 0; i < size; i++)
for (int j = i; j < size; j++)
{
int thisSum = 0;

for (int k = i; k <= j; k++)
thisSum += arr[k];

if (thisSum > maxSum)
maxSum = thisSum;
}

return maxSum;
}

public static int maxSubSum2 (int[] arr)
{

int size = arr.length;

int maxSum = -1;

for (int i = 0; i < size; i++)
{
int thisSum = 0;

for (int j = i; j < size; j++)
{
thisSum += arr[j];

if (thisSum > maxSum)
maxSum = thisSum;
}
}

return maxSum;
}

public static int maxSubSum3 (int[] arr)
{
int size = arr.length;

int maxSum = -1;
int thisSum = 0;

for (int j = 0; j < size; j++)
{
thisSum += arr[j];

if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}

return maxSum;
}

}



The Eclipse Java project MaxSum contains the application MaxSubMain. This application contains three different methods:

public static int maxSum1(int[] arr);
public static int maxSum2(int[] arr);
public static int maxSum3(int[] arr);

Each of these takes an int array arr, then finds the largest sum of any consecutive subarray of arr. But there is a big difference in the computational complexity of each – and you will explore these differences in this assignment.


Add a method public static void part1() which:

(a) Reads a length size from the console;
(b) Generates a random int array arr with arr.length == size;
(c) Calls each of the three maxSumI(int[] arr), I=1..3, passing this array;
(d) Prints out an error message if all of the three calls do not compute the same answer.


Add another method public static void part2(), which does the same calculations as in (1), but also iterates over specific array lengths N of 128, 256, 512, 1024, 2048, and 4096, counting the number of array element additions numAdds that are performed for each of the three maxSumI(int[]), I=1..3, then prints out each value of numAdds along with the length N.

For each of the methods, graph N against numAdds (x-axis => N, y-axis => numAdds), then create a Word or other document that contains each of the three graphs.

For each of the three methods, explain why the number of array additions A(N) done for a length N array has computational complexity of O(N) for one method, O(N^2) for another, and O(N^3) for the third, where N = arr.length.

You don't need to give a rigorous argument here; just reason about the given code and how many times the statement adding an array element to a sum is performed. You could drag out a lot of combinatorial calculations and calculate numAdds exactly as a function of N – but you can just reason here "approximately", instead.


If the number of additions A(N) for maxSum1(int[]) were exactly equal to N^3, then A(2*N) == 2^3*N^3 == 8*N^3 == 8*A(N), and would thus be 8 = 2^3 times larger. However, O(N) analysis does not (usually) yield exact counts, but rather an approximate magnitude of the count, with the approximation improving as N increases.

Describe how well your empirical data from Step (2) fits the theoretical values, by examining the growth of A(N) to that of N. That is, compute the ratio of your observed A(N) to A(2*N), A(4*N), etc to what the theoretical value of the ratio. Comment on your results.


Explain why each of the three methods computes the same value. This is difficult to express clearly and rigorously – since it's very much like a math proof. Do the best you can for this questions.

Explanation / Answer

Dear.. import java.util.Random; import static java.lang.Integer.parseInt; import static java.lang.Math.max; public class MaxSubMain { static final int MAX_ARRAY_SIZE=100000; static final int MAX_ENTRY_SIZE=1000; public static int [] randomArray(int n, int maxEntry) { if (n MAX_ARRAY_SIZE) throw new IllegalArgumentException("Array size = " + n + " bigger than MAX_ARRAY_SIZE = " + MAX_ARRAY_SIZE); if (maxEntry > MAX_ENTRY_SIZE) throw new IllegalArgumentException("Max entry size = " + maxEntry + " bigger than " + MAX_ENTRY_SIZE); int [ ]arr = new int[n]; Random R = new Random(); for (int i=0; i= 0: maxSum; return maxSum; } public static int maxSubSum3(int [] arr) { if (arr == null) throw new IllegalArgumentException("arr is null"); if (arr.length > MAX_ARRAY_SIZE) throw new IllegalArgumentException("Array size = " + arr.length + " bigger than MAX_ARRAY_SIZE = " + MAX_ARRAY_SIZE); int maxSum = 0, thisSum = 0; for (int j=0; j maxSum) maxSum = thisSum; else if (thisSum < 0) thisSum = 0; } assert maxSum >= 0 : maxSum; return maxSum; } public static void usage() { System.out.println ("Usagea:MaxSubsequece maxEntry numArrays"); System.out.println (" arraySize - number of elements per array"); System.out.println (" maxEntry - each entry is between -maxEntry and maxEntry"); System.out.println (" numArrays - number of different arrays to test"); System.exit(1); } public static void main(String[] args) { if (args.length != 3) usage(); int n = parseInt(args[0]); int maxEntry = parseInt(args[1]); int num_arrays = parseInt(args[2]); System.out.println("Testing " + num_arrays + " arrays"); System.out.println("Array entries between " + -maxEntry + " and " + maxEntry); System.out.println(n + " elements in each array"); // create num_arrays random arrays and compute the maximum subsequence sum using three different methods for each for (int i=0; i

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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