CIS-5050 Homework #2: Skip Lists

Due: Friday, February 14, 2020

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 same folder where you unpacked the sample project you created for Homework #1. The archive also contains a Skip_List test program that you can use.

    Implement the three procedures Search, Insert, and Delete following the pseudo-code in the skip lists paper. I have created some implementation notes for you.

  2. 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: 2020-02-03
© Copyright 2020 by Peter C. Chapin <pchapin@vtc.edu>