Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 4/28.
boolean search(int key); // returns true if key is found; false otherwise void insert(int key);Use the value of p = 0.5.
To get a sense of the efficiency of a skip list as compared to a simple linked list, I would like you to perform the following experiment. Start with a positive integer n. Insert the elements 1, 2, 3, ..., n (in that order) into a skip list Now search for each of the elements 1, 2, 3, ..., n (in that order). Note the total time it takes to perform all n search operations. Repeat this 10 times (for the same value of n) and report the average value of the total search time for n. Repeat this experiment for the following values of n: 10000, 11000, 12000, ..., 19000. Plot the average search time as a function of n.
Repeat this experiment using a linked list. Use Lafore's linked list class for this. Specifically, for each value of n, insert the elements 1, 2, 3, ..., n (in that order) into a linked list. Then search for each of the elements 1, 2, 3, ..., n (in that order). Measure the total time it takes for all n search operations on the linked list. There is no need to repeat this 10 times and take the average because each run of this experiment (for a particular value of n) will be exactly the same. Repeat this experiment for the following values of n: 10000, 11000, 12000, ..., 19000. Plot the average search time as a function of n.
Comment on how differences between the two plots. Specifically, comment on the rate of growth of the the two plots.
13, 5, 8, 11, 4, 1.