I’ve been messing around in my free time doing a bit of coding for fun and to explore areas of interest. It’s a bit hard to motivate myself to code during my free time considering coding is also part of my day job. But my day job is not very technically interesting, so this is how I get to explore the fun of coding. I’ll briefly describe a few of these projects which I have in mind.

I decided yesterday to rebuild this website using Hugo, while it was originally built using Jekyll. In this post I’ll discuss my experience.

galtonwatson is a Go module in early development which implements efficient algorithms for the generation and manipulation of Galton-Watson 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 d-ary 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.

In my previous post, I discussed the Burrows-Wheeler transform, and embedded an HTML form on the page which dynamically computed the forward and inverse Burrows-Wheeler transforms with an additional move-to-front 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.

• Input
• BWT
• MTF
• BWT+MTF

The above form implements algorithms to code and decode from the move-to-front compression scheme, with or without an additional application of the Burrows-Wheeler transform. These extremely slick algorithms blew my mind when I first heard of them. They are currently in use, among other places, in [bzip2](https://en.wikipedia.org/wiki/Bzip2) file compression.