For this exercise, we will look at algorithm performance by observing which of the three algorithm runs the fastest. We will compare each algorithm using data sets that increase in size. This performance is determined by running the algorithm and measuring how long it takes to complete each data set in milliseconds (ms).

The PerformanceTest program in the "week04$algoanalysis" package , contains three methods that implement the algorithms(solutions) for computing the range of numbers in an array. The Range_RunTimes EXCEL file, contains the run time data of the three (3) algorithms listed above for a specific computer. There are three (3) different spreadsheets, one for each algorithm. Note the fourth (4th) spreadsheet combines the data for all three algorithms on one graph, however, algorithm 3 uses the secondary scale at top and right of graph.

Instructions : Run the PerformanceTest on your computer and compare it with the data from the PerformanceTest provided. Answer the questions below in the EXCEL spreadsheet. Make sure to save the original so that you can compare it to your test run. Also, answer the questions below in a document and convert both the EXCEL file and the Text document into one PDF Document and Submit. Failure to submit ONLY ONE pdf document on Canvas results in an automatic 20% deduction.

WRITE IN JAVA!

Questions/Analysis

Instructions : Answer the questions after running the PerformanceTest program.

How similar or different is the performance of the data shown in the EXCEL file compared to your results?

What do observe for each of the algorithms shown with their corresponding data set?

Can you tell which algorithm was the most efficient?

For algorithms 1 and 2, did reducing the amount of computations by half improve the runtime significantly? Explain your reasoning, if you felt it had a small or large change.

For algorithms 2 and 3, did reducing the number of loops improve the runtime significantly? Explain your reasoning, if you felt it had a small or large change.

Finding the "Range" of a List of Integers

The range is the difference between the highest and lowest numbers in the array.

Algorithm 1 : Range1

Description: This algorithm uses nested loops to examine every pair of elements in the array , computing their difference and remembering the largest difference found.

maxDiff = 0; for (each index i) for (each index j) update maxDiff, if elements i and j differ more than max.

Algorithm 2 : Range2

Description: This algorithm reduces the amount of computations performed by disregarding one of the (i, j) and (j, i) pairs, that give identical comparisons. It still uses nested loops to examine every pair of elements in the array but now only once, computes their difference and remembering the largest difference found.

maxDiff = 0; for (each index i) for (each index j = i + 1) update maxDiff, if elements i and j differ more than max.

Algorithm 3 : Range3

Description: This algorithm uses a loop to find the largest value and smallest value in the array, compute their difference and return this difference.

max = element[0] min = max for (each index i) find max. find min. return max - min 

Where to find data in my-work

folder > data > Range_RunTimes.xlsx

Where to find starter code in my-work

package.class : week04$algoanalysis.PerformanceTest

Task List

Run the PerformanceTest program and run the data sets listed for each of the range algorithms on your computer. Write a short summary (4-5 sentences is enough) of your observations when running program for the three (3) algorithms.

Modify the Range_RunTimes EXCEL file to also include your data and compare it with the previous data.

If you are experiencing an OutOfMemoryError : Java heap space for your PerformanceTest program. This is possibly due to your Java Virtual Machine (JVM) needing more memory to run this application. You can change your VM options -Xmx2048 to something larger e.g. -Xmx4800m or -Xmx6200m etc. In Java, the -Xms and -Xmx flags are used to set the initial and maximum size of the Heap memory.

To change VM options in INTELLIJ, GOTO> Run->Edit Configurations->Modify Options->Add VM Options and add -Xmx3800m or -Xmx4800m. In IntelliJ, you only need to set the max heap memory size to get things working but you can also use -Xms512s -Xmx4800m depending on set up. If you still have issues increase max heap memory to -Xmx6400m or greater value. If your computer is say over say 10 years old, there may be no hope for you, since your memory will be definitely maxed out long before this!

You can also GOTO> Settings > 'Edit Custom VM Options' and update to VM options -Xmx2048 to something larger e.g. -Xmx4800 etc.

STARTER CODE:

package week04$algoanalysis; public class PerformanceTest { public static int[] dataSet(int n) { long startTime = System.currentTimeMillis(); //Just some Tom Foolery I drummed up int[] data = new int[n]; //begin the Tom Foolery for (int i = 0; i  max) { max = data[i]; } else if(data[i] 
 
 
WHERE TO FIND DATA IN MY-WORK: