CS 2401 Assignment #3

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:

  1. 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.
  2. Second, assume that the list is given as a sorted array. In this case, we can use binary search.
  3. Third, assume that the list is given as a linked list. In this case, we also need to use linear search.
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: 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.

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.