CS 2401 Assignment #3

Due Date: Monday, February 21 or Tuesday, February 22, 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.

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 0, 1, 2, 3, ..., n - 1, n, 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.