Description
Write a program that will perform the following tasks, in turn
Randomly generates n integer numbers (to avoid duplicates, we want the range of the
data be much greater than the size of the data) and save them in an array data structure
Sort these numbers in order
Randomly generate m numbers, for each number, perform the following two search
algorithms on the array, record the actual search time (either target is found, or not).
3.1 linear search algorithm
3.2 binary search algorithm
4. create a report that has the following format: (see the attached file).
Unformatted Attachment Preview
CS520 Algorithm Analysis
Programming Assignment 2 – Run Time Observation
25+5 points
Write a program that will perform the following tasks, in turn
1. Randomly generates n integer numbers (to avoid duplicates, we want the range of the
data be much greater than the size of the data) and save them in an array data structure
2. Sort these numbers in order
3. Randomly generate m numbers, for each number, perform the following two search
algorithms on the array, record the actual search time (either target is found, or not).
3.1 linear search algorithm
3.2 binary search algorithm
4. create a report that has the following format:
Data size (n)
100
search entries
(m)
50
10,000
1000
1e6
1000
1e8
1000
# of found
Average time spent
linear search
Average time spent
binary search
Items to be submitted
1. source code(s)
2. a document that contains the report table
3. a readme file that simply explains how to run the code
Extra credit:
Add a space observation component in your project, so for each data size, you also report how much
memory is used.
Hint:
Refer to StopWatch.java file for managing time stamps.
Refer to http://www.javamex.com/classmexer for measuring memory usage.
Purchase answer to see full
attachment
