Skip to content

Chapter 4: Randomization

4.1 Ordered Statistics

find-max

find-min-max

find-median

4.2 Quicksort

4.3 Shuffling an Array

4.4 Equal Multivariate Polynomials

4.5 Hash tables

4.6 Skip Lists

a method of skip list implementation : implement lookahead single-linked linked list, then test , then transform to skip list implementation , then same test, then performance comparison

Role of Randomness

concurrent access application

Idea for an exercise

4.7 Treaps

java example of treap implementation

Treaps compared and contrasted to Splay trees

4.8 Derandomization

4.9 Exercises

4.10 Supplementary Topic: skip lists and multiprocessor algorithms

Lock-free programming issues