This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

# Skip list gallop search

Due: February 23
Points: 4

We know from class that searching for an item in a skip list takes expected $$O(\log n)$$ time. But what if the item we are searching for is known to be near the beginning of the skip list?

Define k as the index of whatever we are search for in the skip list. So for example if we're search for the 2nd smallest thing in the skip list, $$k=2$$. Devise a simple algorithm to search for the kth smallest thing in a skip list that has expected running time $$O(\log k)$$. Describe your algorithm in pseudocode and with a well-chosen example to show how it works.