CMSC 341    Spring 2007    Project 5

**************************************************************
*                                                            *
*   YOUR NAME HERE:                                          *
*                                                            *
**************************************************************

Your answers need not be very long, but they must be relevant
and complete.  Answers should not consist only of code.  They
should be short English explanations that show you know what
you are doing in the code.  

Include the output from at least 6 runs of your program
(three with p = 0.25 and three with p = 0.5).  Your runs should insert
a large number of integers (at least 5000) and vary the max node size.
----------------------------------------------------------

1) What is the average asymptotic  number of comparisons as a 
function of list size?  Justify your answer.  Do your data 
support this theoretical result?  Justify your answer.

2) Answer question (1) again for an ordinary linked list.  Hint: you do not
have to write or use any additional linked list code.  Use your
SkipList code.

3) What does "number of comparisons" have to do with time performance
of the SkipList operations find and insert?  Why not just
measure the time directly?

4) Does the average number of pointers meet your theoretical
expectations as a function of probability level?  Explain, stating the
theory and giving relevant data from your program.

5) Do the node size distributions agree with your theoretical
expectations? Explain, stating the theory and giving relevant data
from your program.