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.

Problem 43

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.