A quick primer on Graphviz

September 30, 2014

One of the tools I use to make figures for papers and books—if I need to make a graph, of course—is Graphviz. Graphviz is flexible, powerful, but also a rather finicky beast that will repeatedly bite your fingers. Today, I’ll share some of my tricks with you.

graphe-rename-2

Read the rest of this entry »


The Zero Frequency Problem (Part I)

September 23, 2014

In many occasions, we have to estimate a probability distribution from observations because we do not know the probability and we do not have enough a priori knowledge to infer it. An example is text analysis. We may want to know the probability distribution of letters conditional to the few preceding letters. Say, what is the probability of having ‘a’ after ‘prob’? To know the probability, we start by estimating frequencies using a large set of observations—say, the whole Project Gutenberg ASCII-coded English corpus. So we scan the corpus, count frequencies, and observe that, despite the size of the corpus, some letter combinations weren’t observed. Should the corresponding probability be zero?

Read the rest of this entry »


Jouette’s Attractor

September 16, 2014

I have been reading a lot of mathematical recreation books of late. Some in English, some in French, with the double goal of amusing myself and of finding good exercises for my students. In [1], we find the following procedure:

Take any number, n digits long, make this number t. Make t_1 the number made of the sorted (decreasing order) digits of t, and t_2, the number made of the sorted (increasing order) digits of t. Subtract both to get t': t'=t_1-t_2. Repeat until you find a cycle (i.e., the computation yields a number that have been seen before).

Jouette states that for 2 digits, the cycle always starts with 9, for 3 digits, it starts with 495, for 4 digits, 6174, and for 5 digits, 82962. For 2, 3, and 4 digits, he’s mostly right, except that the procedure can also reach zero (take 121 for example: 211-112=99, 99-99=0). For 5 digits, however, he’s really wrong.

Read the rest of this entry »


Perfect Hashing (part I)

September 9, 2014

A few days ago, a friend asked me how to write, if even possible, a hash function that had no collisions. Of course, it’s relatively easy to get a reasonably good hash function that will give the expected amount of collisions (especially when used as usual, modulo the size of the table). But what if we do not want collisions at all? What can we do?

7e4156dfac4d82e9a5cab4987ecc3a15

There are some hash functions, known as perfect hash function, that will yield a different hash for every key from a a priori known set of keys, say K. Are they hard to build? Fortunately, not really. Can we exploit the uniqueness of the hashed value to speed look-ups up? Yes, but it’s a bit more complicated.

Read the rest of this entry »


Take That, Fermat!

September 2, 2014

You’ve certainly heard of Fermat’s last theorem stating that

x^n+y^n=z^n

has no integer solutions for n\geqslant{3}. Well, guess what:

85751^{12} + 95642^{12} = 97565^{12}.

Take that, Fermat!

Read the rest of this entry »