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 49

k-level skip list

Due: March 1
Points: 2

(Note: you should probably start by doing Problem 41.)

What if a skip list were restricted to k levels, for some constant k? What would be the optimum way of storing n items in a skip-list of height k, and what would the resulting cost of search, insert, and delete be?

Describe the data structure construction (briefly). Give a big-O bound in terms of n and k. Then show how this relates to the usual skip list with expected height \(k = \lg n\).