Computer Science 410: Homework 8
The Skip List

Homework 8: Handed out: 4/8/99; Due: 4/15/99

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 a run time analysis of it.

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 a running time analysis of the same.

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 run time analysis...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
• Timing Graphs and analysis - 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

Create a local folder with your NetID (your login) as its name. Set the permissions everyone can read it. Then copy your project folder containing all .java, .class, and MS Visual J++ files into the folder \\goose\courses\CS410\A3\Submissions

If you make a mistake and wish to resubmit, submit with a number after your netid.
For example jjj21_1. We will read the code with the highest number.

Grading Scheme

• 50% correctness of SkipList operations
• 40% 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
• You can email Indranil Gupta or Lantian Zheng