Restrictions: you cannot use any methods from the Java Array$($s$)$ class to copy an array, check for equality, or otherwise manipulate an array. You must write the Java code to perform these functions.

Allowed imports:

$$ java.util.Random

Create a NetBeans project named Lab$105$ and ensure it is saved to a location like desktop or your flash drive. In the project you will do the following:

In this assignment you are to:

$$ Implement the five methods in Code Fragment $4\mathrm{.}12$ on page $183$ of the textbook.

$$ Measure the run times for each algorithm as the number of items they process increases, i$.$e$.$ as N increases, storing your results in a two$-$dimensional array.

$$ Use the System.nanoTime$()$ method to measure the run times.

$$ Display your results in a correctly formatted ASCII table.

Create a Client Class that will time each of the algorithms for increasing values of N

$$ N should start at $2$ and double on each pass

$$ For each pass create array$($s$)$ of random integers to use as test data.

$$ You may want to set the maximum value of N at less than $30,000.$ This took $9$ minutes to run on my system.

$$ Once you have collected all of the results display the results in a correctly formatted ASCII table. See example below.

$$ You must use the System.out.printf$()$ method to print your table.

$$ Note that the width of each column in the table is determined by the width of the widest value in that column

$$ Each data row is separated by a separator row made up of $-$ and $+$ characters

$$ On each data row the values are separated by a $|$

$$ Each data value has two blank spaces before and after the value $($cell padding$)$

$$ The $+$ characters in the separator rows line up with the $|$ symbols in the data rows

$$ The table begins and ends with a separator row

$$ The numerical values line up vertically

o Numerical values are displayed with the thousand comma separator

o For your table to display correctly in your word document you must set your font to $$Courier New$$ or some other fix$-$width font

o You may also need to set the row space to $0$ for both before and after

The data displayed in this example are for illustrative purposes only.

Your results might or might not match the values give in the example.

$+---------+----------+----------+-----+-----+---------+$

$|2|1,500|2,600|0|0|0|$

$+---------+----------+----------+-----+-----+---------+$

$|4|300|500|0|0|0|$

$+---------+----------+----------+-----+-----+---------+$

$|8|500|500|0|0|0|$

$+---------+----------+----------+-----+-----+---------+$

$|16|1,100|1,000|0|0|1|$

$+---------+----------+----------+-----+-----+---------+$

$|32|900|900|0|0|0|$

$+---------+----------+----------+-----+-----+---------+$

$|64|800|600|0|0|1|$

$+---------+----------+----------+-----+-----+---------+$

$|128|1,400|1,300|0|0|1|$

$+---------+----------+----------+-----+-----+---------+$

$|256|2,500|1,400|0|0|5|$

$+---------+----------+----------+-----+-----+---------+$

$|512|5,000|2,600|0|0|29|$

$+---------+----------+----------+-----+-----+---------+$

$|1,024|9,200|4,600|1|0|119|$

$+---------+----------+----------+-----+-----+---------+$

$|2,048|17,900|9,500|0|0|934|$

$+---------+----------+----------+-----+-----+---------+$

$|4,096|34,300|17,600|1|0|7,408|$

$+---------+----------+----------+-----+-----+---------+$

Things to turn in:

$$ Open a Microsoft Word document name using the following file naming convention

o i$.$e$.$ Lab$105-$LnameFM

$$ Lab$105=$ assignment prefix