CMSC 341 -- Spring 2004 -- Project 4 Questions

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

These questions count for 10% of your project grade.

1. (10 points) Run your program with S = 12345 and N = 511.
   Then answer the flowing questions based on the statistics 
   collected. 
   1) On average, the total number of comparisons for constructing 
      a BST by inserting N random integers is O(Nlog N), and the
      average number of comparisons for failed find operations
      in such a randomly constructed BST is O(log N). 
      Do your experiment confirm with these theoretical estimates?
   2) Since the average probes for insert in HT is O(1), the total
      number of probes in constructing the HT with N integers would
      be O(N). Do your experiment results confirm with this theoretical
      estimate with different lambda values?
   3) The quadratic probing supposedly has a better performance than
      linear probing. Discuss whether this is true in your experiment
      with respect to successful and failed find operations with 
      different lambda values?
      For linear probing, the average numbers of probes for 
      successful and failed find are estimated as 
         0.5*(1 + 1/(1 - lambda)) and 0.5*(1 + 1/(1 - lambda)^2).
   [Note: You can use either the lambda values given in the experiment
    or calculate the true lambda by N/M where M is the actual size of
    the HT.]

2. (10 points) Suppose you want to extend your program to compare 
   other probing functions (e.g., linear and double hashing) in 
   addition to quadratic probing. How do you change the author’s 
   code for this?
   [Note: Since except the different probing method is used, all other
    operations are the same, you should not have three copies of code,
    each with a different function.]