CIS-5050 Homework #2: Skip Lists

Due: Friday, September 17, 2021

Read the skip lists paper with special attention to the pseudocode 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.

I provide a package specification and a skeletal package body for Skip_Lists in the samples repository on GitHub. If you do a pull in your clone, you should get the new files. Recall that I recommend creating a branch for each assignment.

Implement the three procedures Search, Insert, and Delete following the pseudocode in the skip lists paper. I have created some implementation notes for you.
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 archive to Canvas.