Computer Science 409: Homework 6
The Skip List

Homework 6: Handed out: 3/13/2001; Due: 3/29/2001

Note:

This assignment involves programming, which will have to be done using J++ in the CSUGLab. Even if you originally use another variant of Java for your program, make sure it runs in the CSUGLab.

As usual, you can discuss this assignment with anyone you like, but you must write it up yourself.

Purpose

This is a simple homework. In this, you will

1. Implement the ADT SkipList, and
2. Do an analysis of the running time.

What you are given

You are given

1. The interface for the Skip list that you have to implement - SkipListInterface.java
2. The skeleton for the SkipList - SkipList.java
3. The Output format class OutputList.java

What you have to do

You have to

• Implement the SkipListInterface

  • Implement the insert, delete and search functions (as discussed in class) into the code skeleton in SkipList.java,
  • Implement the Output() method in SkipList.java, which returns an object of type OutputList (already given to you) reflecting the structure of your skip list at that stage. We will use this to check the validity of your skip list when we test your program (you can use it for testing your code too).
  • The elements you will be storing in the skip list are integers which themselves are the keys.

• Do an analysis of the running time.

More on these

• The class OutputList given to you just contains a Vector array Levels and an integer NumLevels. The method Output() that you implement in your skip list must return an object of type OutputList with NumLevels set to the number of levels in your skip list and Levels pointing to an appropriately filled-up structure reflecting your skip list elements. Each element of the array Levels must point to a level in your skip list (from its left of course), with Levels[0] pointing to the topmost level.
• On the analysis of the running time...this is the part which is totally left to you. At the minimum you have to plot the variation in the running time of carious operations (insert, delete, search) as the number of elements in the skip list is increased.
  • How you chose the element set sizes at which to measure the timings is left to you - your experience from the first programming assignment should help you here. Your aim should be to see the asymptotic logarithmic variation in the running time - try to go to as large set sizes as possible for this.
  • If you take enough readings of the timing at each data-set size, you could even do an analysis of the variance of the running time of the operations.

Write-up

Your report (please limit it to a maximum of 3 pages) should contain...

• Introduction
• Details of your SkipList implementation
• Analysis of the running time (including graphs) - a discussion of graphs is very important. We might not even look at your graphs if you don't point out their salient features.
• Conclusion
• Raw Data

What you need to turn in

Please turn in a hard copy of your code and your report in class and e-mail code to dwh6@cornell.edu . No electronic copy of the report is needed. Of the three given files, the only one you are asked to modify is SkipList.java, so you need to submit only this file, and any original code files you need to write.

Grading Scheme

• 55% correctness of SkipList operations
• 35% for the write-up (general description of implementation, graphs and their discussion)
• 10% coding style (neatness, comments, etc.)

Clarifications/Doubts etc...

• Read the class newsgroup
• Don is the "point person" for this assignment. Questions can be e-mailed to dwh6@cornell.edu