Homework 1

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

This Homework Is Due By 11:59 PM on February 8, 2015

1. Implementation: (15 Points)
   
   In lecture, we reviewed two searching algorithms: Linear Search and Binary Search Write a Java program that implements both linear search and binary search. You may implement either the recursive or iterative version of binary sort.


2. Test Cases: (20 Points)
   
   You must also write a driver program that demonstrates that both searh search programs work. Your driver should use a sorted list of 10,000,000 numbers. Your driver should time how long each algorithm takes to search for the following numbers:
   
   
   1. 500
   2. 10,000
   3. 100,000
   4. 1,000,000
   5. 5,000,000
   6. 7,000,000
   7. 10,000,000
   
   Run each test 10 times and make a table with the running time for each run, as well as the average and the standard deviation for each algorithm.


3. Analysis: (15 Points)
   
   Using the tables you created, answer the following questions using complete sentences:
   
   
   1. Was Linear Search ever faster than Binary Search? When? Explain.
   2. If both searches report the time as 0 milliseconds for an instance, do they take the same amount of time? Why or why not?
   3. Which was the faster search overall? Explain.

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project. The analysis must be a typed Microsoft Word file. No other forms of submission will be accepted.