Reading GPS data with Bash

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.

Breaking Caesar’s Cipher (part III)

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.

Suggested Reading: Lost Cat

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

(Buy at Amazon.com)

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?

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

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 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.

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

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 data items, nodes were allocated (but only contained data; the 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 extra memory.

Caesar’s Cipher

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.