
galtonwatson, a Go module for efficient manipulation of GaltonWatson trees
galtonwatson is a Go module in early development which implements efficient algorithms for the generation and manipulation of GaltonWatson trees. By extension, this tool can be used to generate uniformly random samples from many classes of rooted trees, including:
 uniformly random binary trees of a given size,
 uniformly random dary trees of a given size,
 uniformly random Cayley trees, i.e., unordered labeled trees of a given size,
 uniformly random ordered trees of a given size,
 etc.

The BurrowsWheeler transform, revisited
In my previous post, I discussed the BurrowsWheeler transform, and embedded an HTML form on the page which dynamically computed the forward and inverse BurrowsWheeler transforms with an additional movetofront compression step. My initial implementation of this form was done in pure JavaScript with no particular care for efficiency, and in particular used \(O(n^2 \log n)\) space and time. The new implementation on the same page reduces this complexity to \(O(n \log n)\) time and \(O(n)\) space, making the form usable on larger texts. It is possible, as noted in the paper of Gil and Scott, that this time complexity can be reduced to \(O(n)\) by using linear time suffix array construction algorithms.

The BurrowsWheeler transform and movetofront compression
Bit count:Bit count:The above form implements algorithms to code and decode from the movetofront compression scheme, with or without an additional application of the BurrowsWheeler transform. These extremely slick algorithms blew my mind when I first heard of them. They are currently in use, among other places, in bzip2 file compression.

Splay trees and optimality
The splay tree is probably my favourite data structure. Is it useful in practice? Probably not, but its remarkable optimality properties coupled with its bare simplicity are so tantalizing that I’ve fallen in love with splaying. In the rest of this post, I’ll describe the splay tree structure, and present some of my favourite splay tree properties. You will also find an instructive D3 visualization of a splay tree in motion.

A uniform sum threshold problem
Let \(U_1, U_2, \dots\) be an infinite sequence of independent \(\mathrm{Uniform}[0, 1]\) random variables. Let \(N\) be the minimum index for which \[ U_1 + U_2 + \dots + U_N > 1 . \] What is the expected value \(\mathbf{E}\{N\}\)?