CMSC 341 -- Spring 2005 -- Project 4 Questions

Copy this file into your directory and edit it to add your answers
to the following questions about project 4.

These questions count for 10% of your project grade.

1. (6 points) Run your program with a sample exclusion file and a 
   input file of your choice. The input file should contain, say 1000 
   distinct words or more. Then answer the flowing questions based on 
   the statistics collected from your experiment. 
   1) How many times in the execution that a rehash occurs before 
      lambda, the load factor, reaches 80%? 
   2) Theoretical estimate of average (expected) number of probings is
             (1/lambda)*ln(1/(1 - lambda)) 
             where ln is natural logarithm 
      when clustering does not occur and lambda is small (see P.190 of 
      the textbook).  
      Are your experiment results consistent with the theoretical 
      result? Does the theoretical estimate hold for load factor
      up to 0.25, 0.5, and 0.8?

2. (4 points) What data structure have you chosen for supporting 
   pre-processing? 
   Justify your selection with the time performance in mind.