Bill Teter
Office:          149 Redcay
Telephone:    2782
Office Hours:  Tuesday, Thursday 9:00-12:00

email:  william.teter@plattsburgh.edu

Lab 8 -- complexity of binary and linear search

In this lab you will write a program that puts words from a dictionary into a sorted array.  Then your program will open a test data file that contains one word per line.  Your program will count how many times the compareTo() method is invoked in the process of looking up all the words in the data file using a linear search algorithm.  Print this number to the console.  Then look up all the words again and again keep count of how many times compareTo() method is invoked this time using the binary search algorithm.  Again, print the results.

The dictionary file is  /usr/share/dict/words

The data file is /home/teterwa/public/csc223/lab8/data

You can copy the file          /home/teterwa/public/csc223/lab8/Test.class
to your home directory and run it.

Suggested design:

The Test program should have three static methods and a static array that holds the words from the dictionary file.  The static methods will create the array, do the linear searches and then do the binary searches.  The template for this program can be copied from /home/teterwa/public/csc223/lab8/Test.java

How are you going to count how many times compareTo() is invoked?  One way would be to create a static int count field in the Test program and then modify the code for both the linear search and the binary search to increment this count field each time compareTo() executes.  A clever solution which requires no modification of the search codes is to create a new String class called, perhaps MyString, which implements Comparable<MyString>.  This class will have a String field and a static int count field.  Since this class implements Comparable it will have to implement compareTo() .  In compareTo() you can increment the count field.   The class should also contain a static getCount() accessor method and a static method resetCount() that sets the count field back to zero.  The constructor for the class would have a String parameter which would be assigned to the String field in the class.  The the Test program would convert all the words in the dictionary into MyString objects and all the words on the data file into MyString objects as well.

If you use the clever solution to counting compareTo()'s you can use the binarySearch() method that is in the Arrays class in the java api.  Otherwise code your own version (page 185.)

Sample code for reading lines from a file is on page 56.