Task 2: Quadratic Growth - Two sum problem Replace the sum of the first N integers with the two sum method brute force (https://algs4.cs.princeton.edu/14analysis/TwoSum.java.html). Be sure you...

Task 2: Quadratic Growth - Two sum problem

1. Replace the sum of the first N integers with the two sum method brute force (https://algs4.cs.princeton.edu/14analysis/TwoSum.java.html). Be sure you generate randomly the array for each trial in a similar way like in: (https://algs4.cs.princeton.edu/14analysis/DoublingTest.java.html). Create a single test to check the order of growth.


2. Identify which are good initial values, increment and end value for your growth table. Analyze the data and explain how you validate tha the method has quadratic growth. Create another growth table, with different initial, increment and end values, and repeat the process. Which experiment is bettter? Why? Include the growth table and your answers in the PDF


3. Modify the method to run faster, in linearithmic growth, usinghttps://algs4.cs.princeton.edu/14analysis/TwoSumFast.java.html. Perform the same type of analysis as in the point b above. Include the growth table and your answers in the PDF

Task 3: Cubic Growth - Three sum problem

1. Create a growth table for the three sum problem:https://algs4.cs.princeton.edu/14analysis/ThreeSum.java.html. Create a single test to check the order of growth.


2. Similar with Task 2b but applied to three sum problem.


3. Similar with Task 2c for:https://algs4.cs.princeton.edu/14analysis/ThreeSumFast.java.htmlwith an expected theoretical time of N²logN

/** * */ package a02_analysis_of_algorithms.time_growth_analysis.t1a_sum41; import a02_analysis_of_algorithms.measure_execution_time.t1a_stopwatch.Stopwatch; import a02_analysis_of_algorithms.measure_execution_time.t2a_stat.TimeAnalysis; /** * @author Salma Almaz * We will be generating a growth table to see how the time is growing, compared with the growth of numbers. */ public class SumGrowthAnalysis { /** * Here is the test addition method that will analyze the execution time when we add N integers. * @param name - This is the name of the test method * @param numberOfExecutions - This calculates the amount of times the test is repeated * to help us find the mean/average time. * @param lastValueAdded - The last value that we add. * @return */ public static TimeAnalysis testAddition (String name, int numberOfExecutions, int lastValueAdded) { Stopwatch watch = new Stopwatch(); //String name = "Add the first " + maxValueAdded + " integers"; TimeAnalysis ta = new TimeAnalysis (name, numberOfExecutions); for (int trial = 0; trial < numberofexecutions;="" trial++)="" {="" watch.startwatch();="" @suppresswarnings("unused")="" double="" sum="0;" for(int="" i="1;"><= lastvalueadded;="" i++)="" {="" sum="" +="i;" }="" long="" time="watch.elapsedTime();" ta.add(time);="" }="" return="" ta;="" }="" **="" *="" we="" start="" from="" an="" initial="" value="" and="" increment="" that="" value="" at="" each="" row.="" *="" we="" will="" then="" increase="" the="" minimal="" value="" and="" it'll="" grow="" until="" we="" reach="" the="" maximum="" value.="" *="" we="" will="" also="" have="" a="" constant="" number="" of="" executions="" for="" all="" the="" values.="" *="" @param="" numberofexecutions="" -="" number="" of="" times="" we="" execute="" the="" trail.="" *="" @param="" minvalueadded="" -="" the="" smallest="" value="" added.="" *="" @param="" maxvalueadded="" -="" grow="" until="" we="" reach="" the="" maximum="" value.="" *="" @param="" increment="" -="" increment="" that="" value="" at="" each="" row.="" */="" public="" static="" void="" printmeanexecutiontimegrowthtable(int="" numberofexecutions,="" int="" minvalueadded,="" int="" increment,="" int="" maxvalueadded)="" {="" string="" name="Add the first " +="" maxvalueadded="" +="" "="" integers="" ";="" system.out.println("="" mean="" execution="" time="" table");="" system.out.println("="" -="" method:="" sum="" of="" first="" n="" integers");="" system.out.println("="" -="" sample="" size="" for="" time="" estimation:="" "+numberofexecutions);="" system.out.println("|------------|--------|------|------|--------------------|");="" system.out.println("|="" n="" |="" mean="" |="" min="" |="" mean="" |="" ci="" |");="" system.out.println("|------------|--------|------|------|--------------------|");="" for="" (int="" n="minValueAdded;"><=maxvalueadded; n+="increment)" {="" string="" name="Add the first " +="" n="" +="" "="" integers="" ";="" timeanalysis="" ta="testAddition(name," numberofexecutions,="" n);="" system.out.printf("|="" %9d="" |="" %6.1f|="" %4d|="" %4d="" |="" (="" %6.1f,="" %6.1f)|="" \n",="" n,="" ta.getmeantime(),="" ta.getmintime(),="" ta.getmaxtime(),="" ta.getminmean999confidence(),="" ta.getmaxmean999confidence());="" }="" system.out.println("|------------|--------|------|------|--------------------|");}="" public="" static="" void="" main(string[]="" args)="" {="" printmeanexecutiontimegrowthtable(41,="" 10000000,="" 10000000,200000000);="" }="" }="" **="" *="" module="" a02:="" analysis="" of="" algorithms="" *="" task="" 1a:="" build="" and="" test="" a="" stopwatch="" *="" *="" */="" package="" a02_analysis_of_algorithms.measure_execution_time.t1a_stopwatch;="" **="" *="" we="" are="" testing="" to="" see="" how="" long="" it="" takes="" for="" our="" code="" to="" execute.="" *="" this="" test="" will="" be="" done="" by="" utilizing="" a="" stopwatch="" to="" see="" the="" execution="" time.="" *="" @author="" salma="" almaz="" *="" */="" public="" class="" stopwatch="" {="" here="" we="" are="" logging="" the="" time="" the="" watch="" started.="" it="" also="" logs="" the="" time="" the="" watch="" restarted.="" private="" long="" starttime;="" here="" we="" are="" creating="" a="" stopwatch.="" this="" is="" a="" constructor,="" that="" starts="" a="" stop="" watch.="" public="" stopwatch()="" {="" startwatch();="" }="" in="" this="" method,="" we="" can="" start="" a="" stop="" watch="" and="" log="" the="" time="" in="" milliseconds.="" public="" void="" startwatch()="" {="" starttime="System.currentTimeMillis();" }="" in="" this="" method,="" we="" calculate="" the="" time="" it="" took="" from="" the="" start="" to="" restart.="" return="" the="" time="" in="" milliseconds.="" public="" long="" elapsedtime()="" {="" return="" system.currenttimemillis()="" -="" starttime;="" }="" }="" **="" *="" */="" package="" a02_analysis_of_algorithms.measure_execution_time.t2a_stat;="" import="" lib.bag.fixedcapacitybag;="" import="" java.util.iterator;="" **="" *="" @author="" salma="" almaz="" *="" */="" public="" class="" timeanalysis="" extends="">{ /** * This method creates the time analysis class. * If there are no executions provided it will throw an exception. * The number of executions is exactly the capacity of the bag. * @param name - This is the name of the algorithm tested. * @param numberOfExecutions - We provide this method with a numberOfExecutions and then it runs it. */ public TimeAnalysis(String name, int numberOfExecutions) { super(numberOfExecutions); if (numberOfExecutions < 1)="" throw="" new="" runtimeexception("at="" least="" one="" execution="" expected");="" this.name="name;" }="" **="" *="" this="" constructor="" allows="" you="" to="" get="" an="" array="" of="" all="" the="" executiontimes.="" *="" this="" constructor="" computes="" the="" statistics="" and="" fills="" the="" bag.="" *="" @param="" name="" -="" this="" is="" the="" name="" of="" the="" algorithm="" tested.="" *="" @param="" executiontimes="" -="" this="" is="" an="" array="" that="" provides="" the="" constructor="" with="" the="" executiontimes.="" *="" the="" executiontimes="" are="" in="" milliseconds.="" */="" public="" timeanalysis(string="" name,="" long[]="" executiontimes)="" {="" this(name,executiontimes.length);="" for="" (long="" v="" :="" executiontimes)="" {="" add(v);="" }="" computestatisitcs();="" }="" **="" *="" we="" are="" going="" to="" compute="" the="" following="" statics:="" *="" mean="" of="" the="" execution="" time="" *="" max="" and="" min="" of="" the="" execution="" time="" *="" the="" standard="" deviation="" *="" the="" confidence="" interval="" *="" *="" we="" will="" do="" this="" computation="" if="" the="" execution="" ended.="" */="" private="" void="" computestatisitcs()="" {="" checkexecutionended();="" has="" this="" execution="" been="" computed="" already?="" if="" (statcomputed)="" return;="" iterator=""> iterator = iterator(); long firstValue = iterator.next(); min = firstValue; max = firstValue; sum = firstValue; /** * We are iterating through the values in the bag. * We check if there is a next value. * If there is a next value, we check if it's greater than the min or less than the max. * We add all the values together, then we take the mean. * */ while (iterator.hasNext()) { long value = iterator.next(); if (min > value) min = value; else if (max < value)="" max="value;" sum="" +="value;" }="" mean="sum" getcapacity();="" **="" *="" variance="" is="" a="" statistical="" method="" to="" show="" how="" far="" the="" value="" is="" from="" the="" mean.="" */="" variance="variance" (getcapacity()="" -1);="" to="" find="" the="" standarddeviation="" we="" take="" the="" square="" root="" of="" the="" variance.="" standarddeviation="Math.sqrt(variance);" here="" we're="" using="" a="" t="" test="" approach.="" double="" e="tValue999(getCapacity()-1" *="" standarddeviation="" math.sqrt(getcapacity()));="" minmean999confidence="mean" -="" e;="" maxmean999confidence="mean" +="" e;="" statcomputed="true;" }="" this="" runs="" if="" needed="" mainly="" the="" first="" time="" and="" returns="" the="" time="" in="" milliseconds.="" public="" long="" getmintime()="" {="" computestatisitcs();="" return="" min;="" }="" this="" runs="" if="" needed="" mainly="" the="" first="" time="" and="" returns="" the="" time="" in="" milliseconds.="" public="" long="" getmaxtime()="" {="" computestatisitcs();="" return="" max;="" }="" this="" runs="" if="" needed="" mainly="" the="" first="" time="" and="" returns="" the="" time="" in="" milliseconds.="" public="" double="" getmeantime()="" {="" computestatisitcs();="" return="" mean;="" }="" this="" runs="" if="" needed="" mainly="" the="" first="" time="" and="" returns="" the="" time="" in="" milliseconds.="" public="" double="" gettimestandarddeviation()="" {="" computestatisitcs();="" return="" standarddeviation;="" }="" this="" runs="" if="" needed="" mainly="" the="" first="" time="" and="" returns="" the="" time="" in="" milliseconds.="" public="" double="" getminmean999confidence()="" {="" computestatisitcs();="" return="" minmean999confidence;="" }="" this="" runs="" if="" needed="" mainly="" the="" first="" time="" and="" returns="" the="" time="" in="" milliseconds.="" public="" double="" getmaxmean999confidence()="" {="" computestatisitcs();="" return="" maxmean999confidence;="" }="" **="" *="" here="" we="" are="" checking="" if="" the="" execution="" ended="" and="" we="" can="" now="" compute="" the="" statistics="" and="" perform="" the="" analysis.="" *="" if="" not="" all="" the="" executions="" are="" conducted,="" we="" throw="" out="" an="" exception.="" */="" private="" void="" checkexecutionended()="" {="" if="" (size()="">< getcapacity())="" throw="" new="" runtimeexception("="" not="" all="" experiments="" performed="" (only="" "="" +="" size()="" +="" "="" out="" of="" "="" +="" getcapacity()="" +="" ")");="" }="" this="" is="" just="" printing="" everything="" that="" was="" computed.="" public="" void="" printstatistics()="" {="" computestatisitcs();="" system.out.println("execution="" time="" analysis="" for:="" "="" +="" name);="" system.out.println("="" -="" sample="" number="" of="" values=" + size()); System.out.println(" -="" sample="" minimum="" execution="" time=" + min); System.out.println(" -="" sample="" maximum="" execution="" time=" + max); System.out.println(" -="" sample="" mean="" value=" + mean); System.out.println(" -="" sample="" standard="" deviation=" + standardDeviation); System.out.println(" -="" mean="" 99.9%="" confidence="" interval:="" ("="" +="" minmean999confidence="" +","="" +="" maxmean999confidence="" +")");="" }="" private="" string="" name;="" private="" boolean="" statcomputed="false;" this="" checks="" if="" we="" already="" conducted="" this="" execution.="" private="" long="" min;="" the="" least="" amount="" of="" time="" it="" took="" to="" execute.="" private="" long="" max;="" the="" maximum="" time="" the="" execution="" took.="" private="" double="" sum;="" private="" double="" mean;="" private="" double="" variance;="" private="" double="" standarddeviation;="" private="" double="" minmean999confidence;="" private="" double="" maxmean999confidence;="" **="" *="" t="" test="" values="" to="" compute="" the="" confidence="" interval.="" *="" these="" values="" are="" based="" on="" the="" degrees="" of="" freedom.="" *="" */="" public="" static="" final="" double="" t999[]="{" 636.6,="" 31.60,="" 12.92,="" 8.610,="" 6.869,="" 5.959,="" 5.408,="" 5.041,="" 4.781,="" 4.587,="" 4.437,="" 4.318,="" 4.221,="" 4.140,="" 4.073,="" 4.015,="" 3.965,="" 3.922,="" 3.883,="" 3.850,="" 3.819,="" 3.792,="" 3.768,="" 3.745,="" 3.725,="" 3.707,="" 3.690,="" 3.674,="" 3.659,="" 3.646};="" **="" *="" these="" values="" are="" from="" a="" pre-published="" table.="" *="" @param="" df="" -="" this="" is="" the="" degree="" of="" freedom="" *="" @return="" -="" returning="" the="" t="" test="" value="" */="" private="" static="" double="" tvalue999(double="" df)="" {="" if="" (df="">< 1)="" throw="" new="" runtimeexception="" ("invalid="" degree="" of="" freedoms");="" if="" (df="">=1000) return 3.3; if (df >=100) return 3.39; if (df >=80) return 3.416; if (df >=60) return 3.490; if (df