Due Date: Parts 1 and 2 are due Thursday, September 22 or
Monday, September 26, depending on the day of your lab. Part
3 is due Tuesday, September 27 or Wednesday, September 28,
depending on the day of your lab.
Objective: The goal of this assignment is to compare the
efficiency of different approaches to one specific problem:
search in a list of strings.
Assignment. Write the following three methods:
Our goal is to compare the speed of these methods. All three methods
run very fast (e.g., take less than a second of computation
time) for small values of the list size n, so it is not possible to
simply time the computations. However, we can estimate the time
accurately by using a system method that will return the current
system time in milliseconds as a long integer:
System.currentTimeMillis(). To estimate the time taken:
- First, assume that the list is given as an un-sorted array.
In this case, we need to use linear search to find an element
in this list.
- Second, assume that the list is given as a sorted array.
In this case, we can use binary search.
- Third, assume that the list is given as a linked list.
In this case, we also need to use linear search.
The difference between the two values is the
total number of milliseconds taken by your method. To get a more
accurate estimate you can run your method several times in a row and
compute the average time taken.
- call this method
before running your method and record the value;
- then run your
- when the method finishes running, call System.currentTimeMillis() again
to get the current time.
To test our methods, let us use a list consisting of elements 1000, 1001, 1002,
1003, ..., 1000 + n - 1 (viewed as strings), and let us search for a randomly selected
element in this list (use random number generator to select the
element). Run your program and compare the times taken
by the three methods for n = 500, n = 1,000, and
n = 2,000. Record your observations and be able to explain what is
happening to your TA when you demo your program.
Hint. To assign to the i-th element s[i] of a string array s
a value corresponding to the integer 1000 + i, we can use the code
s[i] = Integer.toString(1000 + i); a random element of this array is
just an element corresponding to a randomly selected index i.