Posts on Tommy Reddad
https://reddad.ca/post/
Recent content in Posts on Tommy ReddadHugoen-usFri, 09 Aug 2024 00:00:00 +0000Rebuilt this website with Hugo
https://reddad.ca/post/2024-08-09-hugo/
Fri, 09 Aug 2024 00:00:00 +0000https://reddad.ca/post/2024-08-09-hugo/<p>I decided yesterday to rebuild this website using
<a href="https://gohugo.io/">Hugo</a>, while it was originally built using
<a href="https://jekyllrb.com/">Jekyll</a>. In this post I’ll discuss my
experience.</p>galtonwatson, a Go module for efficient manipulation of Galton-Watson trees
https://reddad.ca/post/2020-11-21-galtonwatson-go/
Sat, 21 Nov 2020 00:00:00 +0000https://reddad.ca/post/2020-11-21-galtonwatson-go/<p><a href="https://github.com/tommyreddad/galtonwatson"><strong>galtonwatson</strong></a> 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:</p>
<ul>
<li>uniformly random binary trees of a given size,</li>
<li>uniformly random d-ary trees of a given size,</li>
<li>uniformly random Cayley trees, i.e., unordered labeled trees of a given size,</li>
<li>uniformly random ordered trees of a given size,</li>
<li>etc.</li>
</ul>The Burrows-Wheeler transform, revisited
https://reddad.ca/post/2020-09-27-burrows-wheeler-revisited/
Sun, 27 Sep 2020 00:00:00 +0000https://reddad.ca/post/2020-09-27-burrows-wheeler-revisited/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.The Burrows-Wheeler transform and move-to-front compression
https://reddad.ca/post/2019-08-08-burrows-wheeler/
Sat, 08 Aug 2020 00:00:00 +0000https://reddad.ca/post/2019-08-08-burrows-wheeler/<style type="text/css">
.bit-content {
display: inline;
}
.bit-count {
display: inline;
font-family: Monaco, Menlo, Consolas, "Courier New", DotumChe, monospace;
}
.bit-count-label {
font-weight: 700;
display: inline;
padding-right: 10px;
}
.alphabet-content {
display: table-cell;
width: 100%;
border: 1px solid #e1e1e1;
margin-bottom: 16px;
font-family: Monaco, Menlo, Consolas, "Courier New", DotumChe, monospace;
}
.alphabet {
display: table;
width: 100%;
}
label {
font-weight: 700;
display: table-cell;
width: 1px;
padding-right: 10px;
}
textarea {
width: 100%;
display: block;
height: 300px;
border: 1px solid #e1e1e1;
margin: 0 0 10px;
padding: 10px;
font-family: Monaco, Menlo, Consolas, "Courier New", DotumChe, monospace;
}
.tab-pane {
min-height: 300px;
}
.nav-tabs {
margin: 19px 0px 18px;
visibility: visible;
border-bottom: 1px solid #ddd;
}
.nav-tabs > li.active {
font-weight: 700;
}
.nav-tabs > li {
float: left;
margin-bottom: -1px;
}
.tab-content {
margin-bottom: 10px;
}
</style>
<ul class="nav nav-tabs">
<li class="active"><a data-toggle="tab" href="#input-contents">Input</a></li>
<li><a data-toggle="tab" href="#bwt-contents">BWT</a></li>
<li><a data-toggle="tab" href="#mtf-contents">MTF</a></li>
<li><a data-toggle="tab" href="#bwt-mtf-contents">BWT+MTF</a></li>
</ul>
<div class="tab-content">
<div id="input-contents" class="tab-pane active">
<textarea id="input" placeholder="Text to compress..."></textarea>
</div>
<div id="bwt-contents" class="tab-pane">
<textarea id="bwt" placeholder="Burrows-Wheeler transform to invert..."></textarea>
</div>
<div id="mtf-contents" class="tab-pane">
<div class="alphabet">
<label for="mtf-Sigma">Alphabet: </label>
<input class="alphabet-content" type="text" id="mtf-Sigma">
</div>
<textarea id="mtf" placeholder="MTF-compressed binary to decode..."></textarea>
<div class="bit-count">
<div class="bit-count-label">Bit count: </div><div class="bit-content" id="mtf-count"></div>
</div>
</div>
<div id="bwt-mtf-contents" class="tab-pane">
<div class="alphabet">
<label for="bwt-mtf-Sigma">Alphabet: </label>
<input class="alphabet-content" type="text" id="bwt-mtf-Sigma">
</div>
<textarea id="bwt-mtf" placeholder="BWT+MTF-compressed binary to decode..."></textarea>
<div class="bit-count">
<div class="bit-count-label">Bit count: </div><div class="bit-content" id="bwt-mtf-count"></div>
</div>
</div>
</div>
<script type="text/javascript" src="https://reddad.ca/js/2019-08-08-burrows-wheeler/bwt.js"></script>
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.Splay trees and optimality
https://reddad.ca/post/2019-07-27-splay-trees/
Sat, 27 Jul 2019 00:00:00 +0000https://reddad.ca/post/2019-07-27-splay-trees/<p>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.</p>A uniform sum threshold problem
https://reddad.ca/post/2019-07-22-uniform-sum-threshold/
Mon, 22 Jul 2019 00:00:00 +0000https://reddad.ca/post/2019-07-22-uniform-sum-threshold/<p>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\}\)?</p>Generating spherical points without complex operations
https://reddad.ca/post/2019-07-08-generating-without-complex-operations/
Mon, 08 Jul 2019 00:00:00 +0000https://reddad.ca/post/2019-07-08-generating-without-complex-operations/<p>These days, most of everyone’s favourite languages and libraries for
scientific computing come ready-equipped with random number generators
for most common univariate distributions: the uniform, binomial,
normal, geometric, exponential, beta, etc. In my experience,
multivariate generation is comparatively hit-or-miss. But in any case,
since documentation usually doesn’t specify implementation methods or
running time, you usually can’t be sure of the efficiency of one of
these functions without personally examining some source code, or
being lucky and finding that someone else on StackExchange already
did. Thankfully, when in doubt, one can always refer to the excellent
and totally free book <a href="http://nrbook.com/devroye/">Non-Uniform Random Variate
Generation</a> by my old PhD supervisor Luc Devroye. In
fact, it seems this book is even more than free, as stated in this
plea posted by the author on the book’s webpage.</p>
<blockquote>
<p><strong>I give anyone the permission, even without asking me, to take these PDF files to a printer, print as many copies as you like, and sell them for profit.</strong> If you would like me to advertise the sales points of the hard copies, please let me know. <strong>To the libraries: Please do not charge patrons for copying this book. I grant everyone the right to copy at will, for free.</strong></p>
</blockquote>Discrete minimax estimation with trees
https://reddad.ca/post/2019-06-27-density-trees/
Thu, 27 Jun 2019 00:00:00 +0000https://reddad.ca/post/2019-06-27-density-trees/<p>This morning, I submitted the final version of my paper <a href="https://arxiv.org/abs/1812.06063">Discrete
minimax estimation with trees</a> (Devroye and Reddad, 2019), which is to appear in the Electronic
Journal of Statistics. I think this paper is conceptually quite
interesting, and I’m very happy with the final result, so in this post
I’ll describe some of the main ideas present in the work.</p>Some conditioned Galton-Watson trees never grow
https://reddad.ca/post/2019-06-26-conditioned-gw-trees/
Wed, 26 Jun 2019 00:00:00 +0000https://reddad.ca/post/2019-06-26-conditioned-gw-trees/<p>When programmers hear the phrase “random tree,” they most likely think
of a random binary search tree, i.e., a binary search tree built from
the insertion of a uniformly random permutation of \(n\) keys—denote such
a tree by \(\mathrm{BST}_n\). A mathematician might instead think that a
``random tree’’ is more likely to be a uniformly random tree taken
from some class, like the set of all ordered binary trees with \(n\) nodes—denote
such a tree by \(\mathrm{UNIF}_n\). Of course, neither would be wrong. It
should be clear, though, that these two distributions on the space of
binary trees are quite different. In particular, most undergraduate
students of computer science learn, through the study of
comparison-based sorting algorithms, that
\[
\mathbf{E}\{\mathrm{height}(\mathrm{BST}_n)\} = \varTheta(\log n) ,
\]
and some will learn that
\[
\mathbf{E}\{\mathrm{height}(\mathrm{UNIF}_n)\} = \varTheta(\sqrt{n}) .
\]
Though random binary search trees might seem more immediately relevant
to programmers, uniformly random binary trees are part of a bigger
picture which is comparatively more versatile in the probabilistic
analysis of algorithms. To this end, we introduce the concept of
<em>Galton-Watson trees.</em></p>