CIS-5050 Homework #2: Skip Lists

Due: Wednesday, September 26, 2018

Read the skip lists paper with special attention to the pseudo-code for the Search, Insert, and Delete operations. Chapter 5 in the text discusses the use of probabilistic methods in algorithm design in very general terms. You should review that chapter.

  1. I provide a package specification and a skeletal package body for Skip_Lists in this zip archive. Unpack the archive in the src folder of the sample project you created for Homework #1. Implement the three procedures Search, Insert, and Delete following the pseudo-code in the skip lists paper.

  2. We should verify the correctness of your implementation using testing. For this assignment I will provide a Check package and corresponding test program. In future assignments you will be asked to write this code as well.

  3. We should evaluate the performance of your implementation. We will defer that evaluation until you have implemented red black trees so we can compare the performances of skip lists and red black trees against each other.

Create a zip archive of the files skip_list.ads and skip_list.adb. Submit your achive to Moodle.


Last Revised: 2018-09-26
© Copyright 2018 by Peter C. Chapin <pchapin@vtc.edu>