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 40

Skip list level distribition test

Due: February 23
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.