In Java use The Cubic maximum contiguous subsequence sum algorithm, the Quadrati
ID: 639971 • Letter: I
Question
In Java use The Cubic maximum contiguous subsequence sum algorithm, the Quadratic maximum contiguous subsequence sum algorithm, the linear maximum contiguous subsequence sum algorithm, the simple Demonstration of Arrays and the Sample code for time of Execution to create one single application that compares the processing times of each algorithm against the same array of numbers. The application needs to be run with and array of five (5), twenty (20), fifty (50), and one hundred (100) random integers with the range of integers between -10 to 10. Note: The code can be modified between runs to account for the change in array size.
* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
}
return maxSum;
}
* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
}
}
return maxSum;
}
* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSum( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
Simple demonstration of arrays
import java.util.Random;
public class RandomNumbers
{
// Generate random numbers (from 1-100)
// Print number of occurrences of each number
public static final int DIFF_NUMBERS = 100;
public static final int TOTAL_NUMBERS = 1000000;
public static void main( String [ ] args )
{
// Create array; initialize to 0s
int [ ] numbers = new int [ DIFF_NUMBERS + 1 ];
for( int i = 0; i < numbers.length; i++ )
numbers[ i ] = 0;
Random r = new Random( );
// Generate the numbers
for( int i = 0; i < TOTAL_NUMBERS; i++ )
numbers[ r.nextInt( DIFF_NUMBERS ) + 1 ]++;
// Output the summary
for( int i = 1; i <= DIFF_NUMBERS; i++ )
System.out.println( i + ": " + numbers[ i ] );
}
}
Sample Code for time of Execution
long startTime1 = System.nanoTime();
FirstMethodToTime();
long startTime2 = System.nanoTime();
SecondMethodToTime();
long endTimeAll = System.nanoTime();CSCI_2315_Homework2
long duration2ndMethod = (endTime
Explanation / Answer
//Four programs each test the array of size 5,20,50 and 100
//and display the results for each method.
/*
* The java program that displays the time for
* the three algorithms of cubic sum
* and displays the results against
* to 5 for all three metods
* */
import java.text.DecimalFormat;
//CubicSumAlgorithm.java
public class CubicSumAlgorithm
{
public static void main(String[] args)
{
//five (5), twenty (20), fifty (50), and one hundred (100) random
int[] five=new int[5];
DecimalFormat format=new DecimalFormat("##.00");
//Call the createRandomArray with 5,20,50 and 100 for three algorithms
createRandomArray(five);
System.out.printf("%-20s%-20s ","Start Time","End Time(in seconds)");
//Converting from the nano seconds to seconds
int sum=0;
long startTime=System.nanoTime();
sum=maxSubsequenceSum(five);
long endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maxSubsequenceSumOne(five);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maximumSubsequenceSumTwo(five);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
}
/*The method accepts a array of integers an its parameter
* and creats an array with random numbers in a range of
* -10 and 10.
* */
public static void createRandomArray(int[] a)
{
int minimum=-10;
int maximum=10;
for (int i = 0; i < a.length; i++)
{
int randomNum = minimum + (int)(Math.random()*maximum);
a[i]=randomNum;
}
}
/* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
return maxSum;
}
/* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSumOne( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
}
return maxSum;
}
/* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSumTwo( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
}
Sample output for array of size 5:
Start Time End Time(in seconds)
3129.754 3129.754
3129.755 3129.755
3129.756 3129.756
--------------------------------------------------------------------------
/*
* The java program that displays the time for
* the three algorithms of cubic sum
* and displays the results against
* to 20 for all three metods
* */
//CubicSumAlgorithm.java
import java.text.DecimalFormat;
public class CubicSumAlgorithm
{
public static void main(String[] args)
{
//five (5), twenty (20), fifty (50), and one hundred (100) random
int[] twenty=new int[20];
DecimalFormat format=new DecimalFormat("##.00");
//Call the createRandomArray with 5,20,50 and 100 for three algorithms
createRandomArray(twenty);
System.out.printf("%-20s%-20s ","Start Time","End Time(in seconds)");
//Converting from the nano seconds to seconds
int sum=0;
long startTime=System.nanoTime();
sum=maxSubsequenceSum(twenty);
long endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maxSubsequenceSumOne(twenty);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maximumSubsequenceSumTwo(twenty);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
}
/*The method accepts a array of integers an its parameter
* and creats an array with random numbers in a range of
* -10 and 10.
* */
public static void createRandomArray(int[] a)
{
int minimum=-10;
int maximum=10;
for (int i = 0; i < a.length; i++)
{
int randomNum = minimum + (int)(Math.random()*maximum);
a[i]=randomNum;
}
}
/* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
return maxSum;
}
/* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSumOne( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
}
return maxSum;
}
/* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSumTwo( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
}
Sample output for array of size 20:
Start Time End Time(in seconds)
3214.826 3214.826
3214.828 3214.828
3214.828 3214.828
------------------------------------------
import java.text.DecimalFormat;
/*
* The java program that displays the time for
* the three algorithms of cubic sum
* and displays the results against
* to 50 array size
* */
//CubicSumAlgorithm.java
public class CubicSumAlgorithm
{
public static void main(String[] args)
{
//five (5), twenty (20), fifty (50), and one hundred (100) random
int[] fifty=new int[50];
DecimalFormat format=new DecimalFormat("##.00");
//Call the createRandomArray with 5,20,50 and 100 for three algorithms
createRandomArray(fifty);
System.out.printf("%-20s%-20s ","Start Time","End Time(in seconds)");
//Converting from the nano seconds to seconds
int sum=0;
long startTime=System.nanoTime();
sum=maxSubsequenceSum(fifty);
long endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maxSubsequenceSumOne(fifty);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maximumSubsequenceSumTwo(fifty);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
}
/*The method accepts a array of integers an its parameter
* and creats an array with random numbers in a range of
* -10 and 10.
* */
public static void createRandomArray(int[] a)
{
int minimum=-10;
int maximum=10;
for (int i = 0; i < a.length; i++)
{
int randomNum = minimum + (int)(Math.random()*maximum);
a[i]=randomNum;
}
}
/* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
return maxSum;
}
/* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSumOne( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
}
return maxSum;
}
/* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSumTwo( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
}
Sample output of array of siz 50
Start Time End Time(in seconds)
3296.948 3296.948
3296.950 3296.950
3296.950 3296.950
------------------------------------------------------------------
/*
* The java program that displays the time for
* the three algorithms of cubic sum
* and displays the results against
* to 100 array size
* */
//CubicSumAlgorithm.java
import java.text.DecimalFormat;
public class CubicSumAlgorithm
{
public static void main(String[] args)
{
//five (5), twenty (20), fifty (50), and one hundred (100) random
int[] hundred=new int[50];
DecimalFormat format=new DecimalFormat("##.00");
//Call the createRandomArray with 5,20,50 and 100 for three algorithms
createRandomArray(hundred);
System.out.printf("%-20s%-20s ","Start Time","End Time(in seconds)");
//Converting from the nano seconds to seconds
int sum=0;
long startTime=System.nanoTime();
sum=maxSubsequenceSum(hundred);
long endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maxSubsequenceSumOne(hundred);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
startTime=System.nanoTime();
sum=maximumSubsequenceSumTwo(hundred);
endTime=System.nanoTime();
System.out.printf("%-20.3f%-20.3f ",(double)startTime/ 1000000000.0,(double)endTime/ 1000000000.0);
}
/*The method accepts a array of integers an its parameter
* and creats an array with random numbers in a range of
* -10 and 10.
* */
public static void createRandomArray(int[] a)
{
int minimum=-10;
int maximum=10;
for (int i = 0; i < a.length; i++)
{
int randomNum = minimum + (int)(Math.random()*maximum);
a[i]=randomNum;
}
}
/* Cubic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSum( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
for( int j = i; j < a.length; j++ )
{
int thisSum = 0;
for( int k = i; k <= j; k++ )
thisSum += a[ k ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
return maxSum;
}
/* Quadratic maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maxSubsequenceSumOne( int [ ] a )
{
int maxSum = 0;
for( int i = 0; i < a.length; i++ )
{
int thisSum = 0;
for( int j = i; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
}
}
return maxSum;
}
/* Linear maximum contiguous subsequence sum algorithm.
* seqStart and seqEnd represent the actual best sequence.
*/
public static int maximumSubsequenceSumTwo( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
for( int i = 0, j = 0; j < a.length; j++ )
{
thisSum += a[ j ];
if( thisSum > maxSum )
{
maxSum = thisSum;
int seqStart = i;
int seqEnd = j;
}
else if( thisSum < 0 )
{
i = j + 1;
thisSum = 0;
}
}
return maxSum;
}
}
---------------------------------------------------
Sample output of array of siz 100
Start Time End Time(in seconds)
3354.097 3354.097
3354.099 3354.099
3354.099 3354.099
Hope this helps you..
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.