Randomized Algorithms

Redis backs its sorted sets with one. LevelDB and RocksDB use one for their in-memory memtables. Java ships a `ConcurrentSkipListMap` in its standard library because lock-free skip lists are dramatically easier to implement than lock-free balanced BSTs. The structure those production systems share is a **Skip List**: a sorted linked list with a few extra express-lane pointers that turn `O(n)` search into `O(log n)` expected. This lesson covers the multi-level structure (a base list with every element, plus higher levels each containing a random subset that acts as a fast-path index), the coin-flip promotion rule that decides how many levels each new node spans, and search, insert, and delete operations whose expected cost is logarithmic without any tree rotations or balance bookkeeping. You will trace the search path that drops one level at a time whenever the next pointer overshoots the target, and you will analyze why a fair coin produces the right level distribution. In **Linked Lists (Singly)**, a search was `O(n)` because the list offered exactly one pointer per node. A skip list keeps that simple node, just adds a small array of forward pointers to higher levels, and lets randomness substitute for the deterministic balancing that AVL and Red-Black trees rely on. Next, **Balanced BST (AVL / Red-Black)** is the deterministic counterpart: same logarithmic guarantees, fundamentally different implementation strategy.

Implementing a Red-Black tree from memory under interview pressure is a known-hard task; the rotation cases alone are several hundred lines of careful pointer work. A **Treap** reaches the same expected `O(log n)` height in maybe sixty lines, with no color bits and no balance factor, by giving each node a random priority and asking the tree to satisfy two simple invariants at once. This lesson covers the dual structure (BST order on keys, heap order on randomly assigned priorities), the proof sketch that random priorities yield expected `O(log n)` height because the tree is shaped like a uniform random BST, and the two operations that make treaps unusually flexible: `split(key)` cuts the treap into 'less than' and 'greater or equal' pieces, and `merge` glues two treaps together when one contains only smaller keys. From those two primitives, insert, delete, k-th element, and even range reversal fall out naturally. You will also meet the implicit treap, where positions replace keys and the result behaves like a balanced array supporting `O(log n)` insert-at-index and slicing. In **Binary Search Tree (BST)**, you saw that an unlucky insertion order produced a chain; randomized priorities solve that by making any input look balanced in expectation, the same way randomized quicksort tames adversarial pivots. With treaps in hand, the curriculum next explores structures that exploit very different properties (such as bounded integer universes) to push performance beyond what comparison-based trees can offer.

Plain quick sort with a fixed pivot is `O(n log n)` on random input but `O(n^2)` on already-sorted input, the worst-case input an adversary can hand it. Pick the pivot uniformly at random instead, and the same algorithm becomes `O(n log n)` _expected_ on every input, because the adversary no longer knows where the algorithm will partition. Randomization is not a hack here; it is a principled way to break the dependency between input and runtime. **Randomized Algorithms** trains that style of thinking. You will distinguish Las Vegas algorithms (always correct, randomized running time) from Monte Carlo algorithms (bounded running time, possibly wrong) and reason about expected-value guarantees. You will analyze Randomized Quick Sort to see why expected `O(n log n)` is robust against adversarial input, implement Quick Select for `O(n)` expected-time kth-element selection plus the deterministic median-of-medians variant, and walk through Reservoir Sampling Algorithm R for uniformly sampling `k` elements from a stream of unknown length, including the proof of uniformity. The lesson also revisits skip lists and treaps from the data-structures track as randomized alternatives to balanced BSTs. In **Sorting (Elementary)**, you saw worst-case-sensitive sorting. **Recursion Fundamentals** gave you the call-stack model behind quick sort and quick select. This lesson injects controlled randomness into those frameworks. Next, **Approximation Algorithms** trades exactness for polynomial time on NP-hard inputs.