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 Random-Access 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 between 0 and k - 1
    • add k at index j in list (i.e., list.add(j, k))

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

Questions

  1. Compare the preformance of your random permutation generator using a SkipList and LinkedSimpleList for a range of permutation sizes (i.e., choices of n). What is the largest permutation you can generate in approximately 1 second using the LinkedSimpleList? What about for the SkipList?

  2. 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 or response.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.
  • 4 points for responses to the questions above