Assignment 8
 
CS 3500 Assignment #8: Improved hashCode Method and Stress Testing of Red-Black Tree Implementation
Due: Friday, November 15, 2013

The purposes of this assignment are:
  * to improve your hashCode implementation
  * to compare stress testing of binary search tree and red-black tree implementations

Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. You will submit this assignment within Web-CAT.

Your files of Java code should begin with a block comment that lists:
    1.  Your name, as you want the instructor to write it.
    2.  Your email address.
    3.  Any remarks that you wish to make to the instructor.

Part of your grade will depend on the quality and correctness of your code, part will assess the tests you design - especially the test coverage, part will depend on the readability of your code (comments and indentation), and part will depend on how well you follow the procedure above for submitting your work. Assignments submitted between 12:00 am and 11:59 pm the day after the due date will receive a 20 percentage point penalty on the assignment. 

This assignment will have two parts: (1) improving hashCode implementation and (2) stress testing.

--------------------------------------------------------------

Improved hashCode implementation.

Your hashCode implementation should meet the following specs:
    If b1 and b2 are values of the BTree ADT, and

        b1.equals(b2)

    then b1.hashCode() == b2.hashCode().

    If b1 and b2 are values of the BTree ADT, and

        ! (b1.equals(b2))

    then b1.hashCode() is unlikely to be equal to b2.hashCode().

Note:  
The word "unlikely" will be interpreted as follows. 

For every type T, if both b1 and b2 are selected at random from a set of BTree<T> values such that for every non-negative integer n and int value h the probability of a randomly selected BTree b having n == size of b is
    P(n) = 1/2^{n+1} 

and for each element t such that b.contains(t) the probability that 
         h == t.hashCode() is at most 1/5 

and the two probabilities above are independent

then the probability of b1.hashCode() == b2.hashCode() when b1 and b2 are not equal is less than 2%. 

A test program for hashCode probability can be found in the course 
directory:
http://www.ccs.neu.edu/home/vkp/3500-fl13/A8/BTreeHashCodeProbTest.java

--------------------------------------------------------------

Stress Testing

For this assignment, you will be stress testing your implementation of BTree. In order to stress test your red-black tree implementation, you will have to update your stress test program to deal with generics. You will test all of the same tests as were specified in Assignment 5.

You will compare these results to your stress testing in Assignment 5.

Your report of timing output should be submitted as an Excel file. Your file should have two main worksheets---(1) testing on list of words for BST, (2) testing on list of words for RBT,  (3) testing on classical literature for BST, and (4) testing on classical literature for RBT. These worksheets should contain the following headers:
Testing on list of words:
  Comparator, File, Num Strings, Size (#), Build (ms), Iterate (ms), Contains (ms)
Testing on classical literature:
  Comparator, File, Size (#), Build (ms), Iterate (ms), Contains (ms)
  
Along with the four worksheets with the raw data, you should also create charts comparing BST and RBT for each comparator with the text file in which the words are given in that order. For each comparator and text file, you will create two charts: one for build operation and one for contains operation. Therefore you will have six charts. An example is given in the course directory:
http://www.ccs.neu.edu/home/vkp/3500-fl13/A8/implementation_comparison_bst_rbt_build.jpg

If you did not submit data for Assignment 5, you may use my data as your BST data. If you use this data, please note it in the Excel file.
http://www.ccs.neu.edu/home/vkp/3500-fl13/A8/TimingTest_BST_jys.xlsx

--------------------------------------------------------------

For this assignment, you will submit the following:
- Your BTree implementation and test programs
- Your RBTree implementation and test programs
- Your updated stress test program with generics
- Your timing report (Excel file)