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?

      Inserting random integers O(Nlog N):
        -N = 511;   O = 1384;  Actual # = 5994
        -N = 1000;  O = 3000;  Actual # = 11393 
        -N = 15000; O = 62641; Actual # = 254594
      Failed find comparisons O(log N):
        -N = 511;   O = 2.7084; Actual # = 12.9843
        -N = 1000;  O = 3;      Actual # = 13.4295
        -N = 15000; O = 4.1761; Actual # = 19.0940

      No the experiment does not confirm this.  I ran several other experiements
      but none of them support the listed O().  However the experimental results
      do fall between the best case for a balanced tree (O(n log n)) and the
      worse case scenario (O(n^2)).

      
   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?

      Inserting random integers O(N):
        N = 511 ; O(N) = 511
        -Lambda = 0.3;  Actual # = 618
        -Lambda = 0.5;  Actual # = 695
        -Lambda = 0.7;  Actual # = 968

      No, once again the experimental values are higher then O() dictates but
      well beneath the worse case for a unbalanced tree.

   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.]

      Inserting random integers O(N):
        N = 511 
        -Lambda = 0.3; Successful = 1.2142; Failed = 1.5204
                -Experimental: Successful = 1.1984; Failed = 1.3898
        -Lambda = 0.5; Successful = 1.5; Failed = 2.5
                -Experimental: Successful = 1.3813; Failed = 2.0906
        -Lambda = 0.7; Successful = 2.1667; Failed = 6.0556 
                -Experimental: Successful = 1.9222; Failed = 3.4094
      
     Yes the experiment agrees with this proposition.  Particuarly as Lambda
     grows larger the quad probing performs better then linear probing.

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.]
   
      Well you could override the findPos function.  Each overridden method
    could support one of the probing methods (linear, double hashing, quad,
    etc).  You could also call each method using a enum type to specify which
    method.  Of course this could also be done by calling the same function
    with a sentinel value to indicate which probing method should be used.

    The bottom line is that if you want to use a single function to 
    implement multiple probing methods you pass in a sentinel of some type
    and decide which probe to use.  If you do this your will only have to 
    alter a few lines in the findPos function, specifically the lines 
    that set currentPos.  You just have to decide on how to set currentPos
    based on the probe method requested.  If it's linear just increment 
    currentPos until and "EMPTY" is found.  If it's a double hash just
    rehash currentPos using the 2nd hashing function until currentPos != EMPTY.