Assignment 06
A Skiplist
Overview
In class, we analyzed the skiplist data structure and used it to implement the SimpleSSet
interface. In this assignment, you will modify a skiplist to implement the SimpleList
interface.
Background
Recall that the List ADT (defined formally here) represents a list of elements that can be accessed by index. We previously discussed an implementation of the SimpleList
interface using a linked list. The idea was that the head
node stores the value at index 0
, its next
stores the value at index 1
, and so on. A skiplist can similarly be used to represent a SimpleList
. You can read a complete description of the procedure in ODS Section 4.3, SkiplistList: An Efficient RandomAccess List.
Shuffling Numbers
Suppose we would like to store the numbers \(1, 2, 3, \ldots, n\) in a random order—such an ordering is called a permutation of the numbers \(1\) through \(n\). For example, these numbers might represent cards in a deck, and we would like to simulate a perfectly shuffled deck for some game application. One way to accomplish this shuffling using a SimpleList
is to do the following:
 start with an empty
SimpleList<Integer> list
 for
k = 1, 2, ..., n
 pick a random number
j
between0
andk  1
 add
k
at indexj
inlist
(i.e.,list.add(j, k)
)
 pick a random number
After performing these operations, list
will contain every number from 1
to n
exactly once, and all orderings of these numbers will be equally likely. That is, list
will contain a random permutation of the numbers 1
through n
. (There are more efficient procedures for generating random permutations, but this is the procedure you should use for the current assignment.)
Your Task
In this assignment, you will write a skiplist implementation of the SimpleList
interface, called SkipList
. You may write your implementation from scratch, or modify SkipSSet.java
(provided in the code for Lecture 17).
Additionally, you will write a program that that implements the procedure described above to generate random permutations of numbers, stored as a SimpleList<Integer>
. You will compare the performance of the procedure between your SkipList
implementation and the (provided) LinkedSimpleList
implementation we saw earlier in the semester.
Code
 Code for Lecture 17 (including
SkipSSet.java
) SimpleList.java
LinkedSimpleList.java
SimpleListTester.java
Questions

Compare the preformance of your random permutation generator using a
SkipList
andLinkedSimpleList
for a range of permutation sizes (i.e., choices ofn
). What is the largest permutation you can generate in approximately 1 second using theLinkedSimpleList
? What about for theSkipList
? 
A professor decides that students will grade each others’ quizzes in class. To accomplish this, the students hand their quizzes to the professor, who procedes to shuffle the papers in random order. Each student is then given the quiz of a random student in the class. Soon, the professor realizes a problem with this method: there is nothing preventing a student from being handed their own quiz to grade! Apply your random permutation generator to answer the following questions:

If there are 10 students in the class, what is the approximate likelihood that some student is handed their own quiz to grade? What if there 100 students in class? 1,000 students? (Perform many trials to estimate the proportion of trials in which some some student receives their own quiz.)

If there are {10, 100, 1,000} students in class, approximately how many students will on average receive their own quiz? (Again, perform many trials and count the number of students who receive their own quiz in each trial.)

(A permutation of \(1, 2, \ldots, n\) in which no number \(i\) appears in position \(i\) in the shuffled list is called a derangement. The first part of question 2 is equivalent to estimating the probability that a random permutation is a derangement.)
What to Submit
SkipList.java
response.md
orresponse.pdf
containing your responses to the questions above
Evaluation
Your submission will receive a score out of 10 points, broken down as follows:
 6 points for
SkipList.java
 Code compiles, runs, and passes tests in
SimpleListTester.java
.  Code is sensibly organized with helpful comments.
 Code performs the simulations as specified above and reports specified statistics.
 Code compiles, runs, and passes tests in
 4 points for responses to the questions above