Homework 1

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Fall 2015

This Homework Is Due By 11:55 PM on September 18, 2015

1. Implementation:
   
   In lecture, we reviewed two searching algorithms: Linear Search and Binary Search
   Your implementation must be in a class named Search. Your Search class must implement the following methods:
   
   
   1. public static long linearSearch(int[] listOfNumbers, int target);
      
      Input Parameter: int[] listOfNumber - An array of int's.
      Input Parameter: int target - The int to be searched for in listOfNumbers.
      
      Method Returns: a long value containing the number of nano-seconds it took to find specified target within the listOfNumbers. If the target is not found, the method returns a -1.
   
   
   
   2. public static long binarySearch(int[] listOfNumbers, int target);
      
      Input Parameter: int[] listOfNumber - An array of int's.
      Input Parameter: int target - The int to be searched for in listOfNumbers.
      
      Method Returns: a long value containing the number of nano-seconds it took to find specified target within the listOfNumbers. If the target is not found, the method returns a -1.


2. Test Driver:
   
   You must also write a driver program that demonstrates that both searh search programs work. Your driver should use a sorted array of 10,000,000 int's (1 to 10,000,000) and search for the following targets:
   
   1. 500
   2. 10,000
   3. 100,000
   4. 1,000,000
   5. 5,000,000
   6. 7,000,000
   7. 10,000,000
   
   Your driver must be in a class named Driver. Your Driver class must implement the following methods:
   
   
   1. public static int[] getListOfNumbers();
      
      Method Returns: A sorted array of 10,000,000 int values (1 to 10,000,000). If the array was not already initialized the first time the method is called, the method must create, initialize and save the array in a static, private variable within the class. On subsequent calls, the method should return a reference to the variable already created during the first call.
   
   
   
   2. public static void runLinearSearch(int[] listOfNumbers, int target);
      
      Input Parameter: int[] listOfNumber - An array of int's.
      Input Parameter: int target - The int to be searched for in listOfNumbers.
      
      This method with call the linearSearch method of the Search class 10 times. It will save the run time of each call into a static, private array variable that can be obtained by the getRunTimes() method specified below.
   
   
   
   3. public static void runBinarySearch(int[] listOfNumbers, int target);
      
      Input Parameter: int[] listOfNumber - An array of int's.
      Input Parameter: int target - The int to be searched for in listOfNumbers.
      
      This method with call the binarySearch method of the Search class 10 times. It will save the run time of each call into a static, private array variable that can be obtained by the getRunTimes() method specified below.
   
   
   
   4. public static int[] getTargets();
      
      Method Returns: An array of int values containing the targets specified above.
   
   
   
   5. public static long[] getRunTimes();
      
      Method Returns: The array of long values containing the run times from the previous test case.
   
   
   
   6. public static void clearRunTimes();
      
      This method will clear the run times to all zero.
   
   
   
   7. public static void main(String[] args);
      
      This method will be where you run both the linear and binary searches on all the targets and print out the run times for each target in a table format.

Please submit the completed assignment on the Mimir Platform Website .

You must submit your Java programs as a zip file of only the classes specified above.