Problem 33

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Make me a skip list

Due: February 8
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$