Assignment 2 Basic Array and ArrayList data structures

 Assignment 2 – 100/100 points possible 
The goal of this assignment is to become comfortable using the basic Array and ArrayList data
structures and to gain some exposure to sparse arrays. A sparse array is a data structure that
does not require any memory to represent an entry with the value 0, which is useful for lowdensity data. We’ll run a simple algorithm on the two array types as a quantitative experiment
to compare the execution times of the two implementations.
For example, a dense array might look like:
[ 1, 10, 15, 0, 0, 2, 0, 7, 43, 0, 12, 0, 0 ]
The corresponding sparse array, containing all data necessary to expand back to the sparse
representation, night look like:
[ [0, 1], [1, 10], [2, 15], [5, 2], [7, 7], [8, 43], [10, 12] ]
1. [10] Write a Java program that first prompts the user for an integer array length and a
double-precision array density. You will use these values to create the arrays for the
experiment (see parts 2 and 3 below). For example, if the user enters an array length of 100
and a density of 0.1, your program will create arrays of length 100 with on average of 10
random non-zero entries. Catch any exceptions due to the user entering unparsable input and
prompt them to reenter the value(s).
2. [20] Write a function which takes an integer length and an array density of type double as
arguments and returns a new array of type int representing a dense array. For each entry in
the array, compare the density with a random number on the range [0.0, 1.0) (i.e., 0.0 up to,
but not including, 1.0) to determine whether or not the entry should be 0 (hint: see the
java.util.Random class). If the entry should be 0, simply populate the entry as such. If the entry
should be non-zero, populate it with a random integer on the range [1, 1000000] (i.e., 1
through 1 million).
3. [20] Write a function which takes an integer length and an array density of type double as
arguments and returns a new ArrayList representing a sparse array. As above, use the density
to determine whether or not each entry should be 0. If the entry should be 0, simply do nothing
(i.e., don’t add it to the ArrayList). If the entry should be non-zero, store its index and value
(also on the range [1, 1000000]) in the ArrayList (hint: you may want to use an ArrayList of type
int[] – note that this is not the most elegant solution but we have not yet covered objects in
Java). In this way, the returned ArrayList will only require enough memory to hold the non-zero
elements and could be expanded back to dense form if necessary.4. [20] Write a function which takes an int array as an argument and prints the max value in the
array, along with the index of that value in the array.
5. [20] Write a function which takes an ArrayList as an argument and prints the max value in the
array, along with the original index of that value in the array (i.e., the index that you stored in
part 3).
6. [10] Use the System.nanoTime() method to record the amount of time taken to run each of
the above functions (i.e., steps 2-5 above). Print your timing results. Spend some time trying
different combinations of inputs and write your findings in the comments of your code. Which
implementation is faster for various cases? Your output should look something like:
Please array length:
1000000
Enter density:
0.01
createDenseArray() length: 1000000 time: 39323000
createSparseArray() length: 10143 time: 28992000
findMax (array): 999990 at: 677720
dense findMax() time: 4083000
findMax (list): 999908 at: 494143
sparse findMax() time: 1793000