Problem 34

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

# Skip list level distribition test

Due: February 8
Points: 3

Write a Java, C++ or Python program that reads in random bits (0's and 1's, one per line) from standard in, and writes the size of each level of the skip list that WOULD result if we actually created one using those bits.

Start with the top level (the height of the skip list) and be sure to format them in a way that is easy to read.

For example, if the input indicates the following bits:

``````0
1
0
0
0
1
0
1
1
0
1``````

Then the first skip list item will have height 1, the next will have height 3, then height 1, then height 0, then height 1. So the level distribution in this case would be:

``````Level 3: 1 node
Level 2: 1 node
Level 1: 4 nodes
Level 0: 5 nodes``````

And your output should look something like that.

Submit your program according to the instructions on the submit page.