Problem Set 12. Posted 4/20

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.

1. The skip list data structure can be thought of as being a "hybrid'' of a standard linked list data structure and a balanced binary search tree. It was invented by William Pugh, a computer scientist at the University of Maryland. The data structure is very interesting because randomized choices are made as it is being built. Imagine tossing a coin to decide where a new element goes -- roughly speaking, this is what happens in the insert operation in a skip list. This randomized construction keeps a skip list "balanced" and on average all three operations: insert, search, and delete take O(log n) time on a skip list with n elements. A nice description of skip lists (along with pseudocode, C# code, demo applets, etc.) can be found here and here. This problem assumes that you have read these descriptions. Answer the following questions. I am using terminology that appears in the first of the above two articles.
   1. Suppose we modify the randomLevel function so that it always returns 1. Show (using a picture) how the skip list will look after we insert the numbers 5, 4, 11, 20, 14, 15, and 8 into an empty skip list.
   2. Suppose we modify the randomLevel function so that it takes as input, the key of the element to be inserted, and returns 1 if the key is an odd number and return 2 otherwise. Show (using a picture) how the skip list will look after we insert elements with the following keys 5, 4, 11, 20, 14, 15, and 8 into an empty skip list.
   3. Suppose we modify the randomLevel function so that it returns 1 the first time it is called, 2 the second time it is called, 3 the third time it is called, and then 1 (the fourth time it is called), 2 (the fifth time it is called), and 3 (the sixth time it is called), etc. In other words the function just cycles through the values 1, 2, 3, 1, 2, 3, 1, 2, 3, and so on, in that order. Show (using a picture) how the skip list will look after we insert elements with the following keys 5, 4, 11, 20, 14, 15, and 8 into an empty skip list.
   4. If you were to implement a skip list class in Java, what would the data members be? If you use some auxillary (helper) classes, list them as well. Use comments to describe what these data members are meant for.
   5. Assume that the value of the probability p is 1/2. Suppose we insert the numbers 1 through 10 (in some order) into a skip list. What is the probability that all the nodes in the skip list (except the header node) have exactly one next pointer? Would you consider this event likely?

2. Implement a class called skipList into which we want to insert integers. Forget about the delete operation; just implement the search operation and the insert operation. Use the following headers for these functions:

   	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.

3. Here are some questions about binary heaps.
   1. Show all the distinct binary heaps you can make with the elements

      	13, 5, 8, 11, 4, 1.
      

   2. Suppose that we have a binary heap with 64 elements. As discussed in class, in the standard implementation of a binary heap, these elements are stored in an array in slots 0 through 63. Suppose the binary heap has a unique smallest element. What slots could this element occupy?

   ---