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 39

Make me a skip list

Due: February 23
Points: 2

Starting with an empty skip list, draw the structure that results after inserting the following numbers, in this order:

\[[21, 39, 90, 61, 70, 29, 81]\]

Use the following sequence of "coin flips" in determining the height of each tower. (Remember, in our definition of skip list, the height of the new tower is the number of zeros before the first 1 occurs):

\[0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1\]