## Description

This assignment has two parts. Part 1 is an experiment that compares insertion times and search

times of hash data structure, array list data structure, and linked list data structure. Part 2 is an

experiment that compares the running times of four different sorting algorithms.

Part 1 (50 points)

The goal of Part 1 is to give students an opportunity to observe differences among three data

structures in Java – HashMap, ArrayList, LinkedList – in terms of insertion time and search time.

Students are required to write a program named InsertSearchTimeComparison.java that

implements the following pseudocode:

create a HshMap instance myMap

create an ArrayList instance myArrayList

create a LinkedList instance myLinkedList

Repeat the following 10 times and calculate average total insertion times and average

total search times for all three data structures

generate 100,000 random integers in the range [1, 1,000,000] and store them in

the array of integers keys[ ]

// Insert keys one at a time but measure only the total time (not individual insert

// time)

// Use put method for HashMap

// Use add method for ArrayList and Linked List

insert all keys in keys[ ] into myMap and measure the total insert time

insert all keys in keys[ ] into myArrayList and measure the total insert time

insert all keys in keys[ ] into myLinkedList and measure the total insert time

// after insertion, keep the three data structures with all inserted keys.

generate 100,000 random integers in the range [1, 2,000,000] and store them in

the array keys[ ]

// Search keys one at a time but measure only total time (not individual search

// time)

// Use containsKey method for HashMap

// Use contains method for ArrayList and Linked List

search myMap for all keys in keys[ ] and measure the total search time

search myArrayList for all keys in keys[ ] and measure the total search time

search myLinkedList for all keys in keys[ ] and measure the total search time

Print your output on the screen using the following format:

Number of keys = 100000

HashMap average total insert time = xxxxx

ArrayList average total insert time = xxxxx

LinkedList average total insert time = xxxxx

HashMap average total search time = xxxxx

ArrayList average total search time = xxxxx

LinkedList average total search time = xxxxx

You can generate n random integers between 1 and N in the following way:

Random r = new Random(System.currentTimeMillis() );

for i = 0 to n – 1

a[i] = r.nextInt(N) + 1

When you generate random numbers, it is a good practice to reset the seed. When you first create

an instance of the Random class, you can pass a seed as an argument, as shown below:

Random r = new Random(System.currentTimeMillis());

You can pass any long integer as an argument. The above example uses the current time as a

seed.

Later, when you want to generate another sequence of random numbers using the same Random

instance, you can reset the seed as follows:

r.setSeed(System.currentTimeMillis());

You can also use the Math.random( ) method. Refer to a Java tutorial or reference manual on

how to use this method.

We cannot accurately measure the execution time of a code segment. However, we can estimate

it by measuring an elapsed time, as shown below:

long startTime, endTime, elapsedTime;

startTime = System.currentTimeMillis();

// code segment

endTime = System.currentTimeMillis();

elapsedTime = endTime ‐ startTime;

We can use the elapsedTime as an estimate of the execution time of the code segment.

Part 2 (50 points)

The goal of part 2 is to give students an opportunity to compare and observe how running times

of sorting algorithms grow as the input size grows. Since it is not possible to measure an accurate

running time of an algorithm, you will use an elapsed time as an approximation as as described

in the Part 1.

Write a program named SortingComparison.java that implements four sorting algorithms for this

experiment: insertion-sort, merge-sort, quick-sort and heap-sort. A code of insertion-sort is in

page 111 of our textbook. An array-based implementation of merge-sort is shown in pages 537

and 538 of our textbook. An array-based implementation of quick-sort is in page 553 of our

textbook. You can use these codes, with some modification if needed, for this assignment. For

heap-sort, our textbook does not have a code. You can implement it yourself or you may use any

implementation you can find on the internet or any code written by someone else. If you use any

material (pseudocode or implementation) that is not written by yourself, you must clearly show

the source of the material in your report.

A high-level pseudocode is given below:

for n = 10,000, 20,000, . . ., 100,000 (for ten different input sizes)

Create an array of n random integers between 1 and 1,000,000

Run insertionsort and calculate the elapsed time

// make sure you use the initial, unsorted array

Run mergesort and calculate the elapsed time

// make sure you use the initial, unsorted array

Run quicksort and calculate the elapsed time

// make sure you use the initial, unsorted array

Run heapsort and calculate the elapsed time

Note that it is important that you use the initial, unsorted array for each sorting algorithm. So,

you may want to keep the original array and use a copy when you run each sorting algorithm.

You can calculate the elapsed time of the execution of a sorting algorithm in the following way:

long startTime = System.currentTimeMillis();

call a sorting algorithm

long endTime = System.currentTimeMillis();

long elapsedTime = endTime ‐ startTime;

Collect all elapsed times and show the result (1) as a table and (2) as a line graph.

The table should look like:

n

Algorithm

10000 20000 30000 40000 50000 60000 70000 80000 90000 100000

insertion

merge

quick

heapsort

Entries in the table are elapsed times in milliseconds.

The line graph shows the same information but as a graph with four lines, one for each sorting

algorithm. The x-axis of the graph is the input size n and the y-axis of the graph is the elapsed

time in milliseconds. An example graph is shown below:

Input size

Elapsed time

10K 20K . . . 100K

Algorithm 1

Algorithm 2

Algorithm 3

Algorithm 4

Deliverables

You need to submit program files and a documentation files.

Two program files to be submitted are InsertSearchTimeComparison.java and

SortingComparison.java files. If you have other files that are necessary to compile and run the

two programs, you must submit these additional files too

In a documentation file, you must include, for each part, your conclusion/observation/discussion

of each experiment.

Combine all program files, additional files (if any), and the documentation file into a single

archive file, such as a zip file or a rar file, and name it LastName_FirstName_hw6.EXT, where

EXT is an appropriate file extension (such as zip or rar). Upload it to Blackboard.

Grading

For both parts, there is no one correct output. As far as your output is consistent with generally

expected output, no point will be deducted. Otherwise, 10 points will be deducted for each part.

If your conclusion/observation/discussion is not substantive, points will be deducted up to 10

points.

If there is no sufficient inline comments, points will be deducted up to 20 points.