Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 271-278 (Section 7.4-7.5)

(2nd) pages 399-404 (Section 9.2), pages 362-365 (Section 8.6)

Additional material

PseudoRandomNumberGenerator.java
Math.random()
java.util.Random

Implementation of a dictionary by means of a skip list in PostScript and PDF.

Question

How many (non-dummy) nodes has the first (lowest) level of a skip-list? On average, how many (non-dummy) nodes has the second level of a skip-list? On average, how many (non-dummy) nodes has the ith level?