Reading GPS data with Bash

April 30, 2013

I am presently working on something that requires geolocation. Not knowing much about GPSes and related topics, I decided to get a USB GPS. This week, let’s have a look at how we can extract information from the USB GPS using Bash.


The first step is to locate your USB GPS as a device. If it’s NMEA compliant, it should mount automagically as a USB serial port. You would think that lsusb -v would show you the device, but it does not always. Sometimes it shows as “Brand X GPS”, sometimes it only shows as a generic device, say “MediaTek Inc.”, or even as a modem. It will typically show up as /dev/ttyUSB0 or /dev/ttyACM0.

Read the rest of this entry »

Breaking Caesar’s Cipher (part III)

April 23, 2013

In the last installment of this series, we looked at Markov chains as a mean of estimating the likelihood of a given piece of text of actually being a message, written in English, rather than mere gibberish.

This week, we finally piece everything together to obtain a program to crack Caesar’s cipher without (much) human intervention.

Read the rest of this entry »

Suggested Reading: Lost Cat

April 21, 2013

Caroline Paul, Wendy MacNaughton — Lost Cat: A True Story of Love, Desperation, and GPS Technology — Bloomsburt, 2013, 176 pp. ISBN 1608199770

(Buy at

(Buy at

This is a story of Tibia the cat that suddenly vanishes for five weeks before coming back. In full health, shiny coat, happy. Then vanishes again. Quickly, Caroline Paul catlover, couchridden following a plane crash, worries about Tibby, wondering where he was and why he didn’t come back sooner. Then begins a detective story: will a GPS and a camera attached to the cat reveal its whereabouts?

Read the rest of this entry »

Breaking Caesar’s Cipher (Caesar’s Cipher, part II)

April 16, 2013

In the last installment of this series, we had a look at Caesar’s cipher, an absurdly simple encryption technique where the symmetric encryption only consists in shifting symbols k places.


While it’s ridiculously easy to break the cipher, even with pen-and-paper techniques, we ended up, last time, surmising that we should be able to crack the cipher automatically, without human intervention, if only we had a reasonable language model. This week, let us have a look at how we could build a very simple language model that does just that.

Read the rest of this entry »

Building a Tree from a List in Linear Time (II)

April 9, 2013

Quite a while ago, I proposed a linear time algorithm to construct trees from sorted lists. The algorithm relied on the segregation of data and internal nodes. This meant that for a list of n data items, 2n-1 nodes were allocated (but only n contained data; the n-1 others just contained pointers.


While segregating structure and data makes sense in some cases (say, the index resides in memory but the leaves/data reside on disk), I found the solution somewhat unsatisfactory (but not unacceptable). So I gave the problem a little more thinking and I arrived at an algorithm that produces a tree with optimal average depth, with data in every node, in linear time and using at most \Theta(\lg n) extra memory.

Read the rest of this entry »

Caesar’s Cipher

April 2, 2013

Julius Caesar, presumably sometimes during the war in Gaul, according to Suetonius, used a simple cipher to ensure the privacy of his communications.


Caesar’s method can hardly be considered anything close to secure, but it’s still worthwhile to have a look at how you can implement it, and break it, mostly because it’s one of the simplest substitution ciphers.

Read the rest of this entry »