Adaptive Queries

Jeremy Kun has an amusing and startling trick: pick any polynomial \(p(x)=c_{0}+c_{1}x+\cdots+c_{n}x^{n}\) where the \(c_{i}\) are non-negative integers and the degree, \(n\), is any positive integer you like. Kun will then ask you one at a time for the value of \(p(x)\) at certain points. That is, he will ask for \(p(x_{1}), p(x_{2}), \ldots , p(x_{k})\) for \(x_{i}\) of his choosing. What is the minimum number of points he will have to ask you about to discover the polynomial?

The answer will surprise and delight you. There isn’t any heavy duty mathematics involved so everyone can enjoy the fun. Head on over and be surprised.

Posted in General | Tagged | Leave a comment

query-replace in Emacs 25.

A nice feature of the query-replace function is that you can scroll through the history of previous parameters and perhaps avoid retyping them. Unfortunately, you can’t edit that history so if your new input is even a little bit different, you have to retype it. I’ve often wished for a little more flexibility in that area.

Artur Malabarba brings happy news: In Emacs 25 query-replace history is editable. Even nicer, you will be able to switch the arguments. That’s another thing I’ve often wanted to do. I can hardly wait.

This is the first in a series Malabarba is doing on the new features of Emacs 25. Though it’s doubtless some time away, I’m looking forward to getting my hands on these enhancements.

Every once in a while you hear some young whipper-snapper using Eclipse or some other horror claim that Emacs is old technology and essentially dead. The vigorous development going on in the Emacs community shows how wrong this is.

Posted in Programming | Tagged | Leave a comment

They’re Doing it for Your Own Good

Britain calls forth the four horsemen and apparently without shame or self awareness.

Posted in General | Tagged | Leave a comment

The Problems with Gratuitously Collecting Data

Over at Neustar Research, Anthony Tockar has an interesting if terrifying post on the analysis of anonymized data from New York City’s Taxi and Limousine Commission. The data, which was obtained through a FOIA request, contains details of every Taxi or limousine ride in the city for 2013. The details included the pickup and dropoff times and locations, the fare, the tip, and a anonymized identifier obtained by hashing the taxi’s license and medallion numbers. The first thing that happened was that a hacker used a little thought and completely de-anonymized the data. Once you know how the anonymizing ID was calculated it’s easy to see how this could be done.

Right away you know the annual earnings of the city’s cab drivers but the massive privacy fail doesn’t end there. Tockar, who’s a graduate student in Data Science interning at Neustar was able to tease an unbelievable amount of information from the data. For example, he was able to identify the name, address, property value, relationship status, court records, and a profile picture of an individual who had been frequenting certain men’s clubs. All this information was easy to obtain once Tockar had linked the clubs and a residential address. He was also able to trace the coming and goings of some celebrities from the city. Read his post for the details and how he was able to leverage the data to reveal all sorts of private information.

Tockar’s solution to this is something called differential privacy. It’s analogous to the selective availability that the U.S. government used to use to perturb the accuracy of the (commercial) GPS system. The idea is that the coordinates of the locations are perturbed by random noise so that the locations can not be tied to individuals.

To me, this misses the point. The problem with this sort of data is that someone will always abuse it. Even if the data hadn’t been released, it was still available to city authorities who could use it to track individuals or otherwise spy on citizens’ activities—probably without a warrant. Imagine a jealous spouse or partner, for example, who worked at the commission, had access to the data, and used it to track the object of his or her jealousy.

The only real solution to the problem is to not collect the data to begin with. Did the city have any real reason for its collection other than that they could? If asked they’d be sure to bring up the usual four horsemen but the relevant information is kept by the drivers in their trip logs and can be obtained from them in the rare cases that it’s needed. Centralizing the data and subjecting it to FOIA requests is just asking for trouble. Trouble, that as Trockar demonstrates, is easy to find.

Posted in General | Tagged | Leave a comment

Lisp and Mathematics

I’ve written many times about Atebey Kaygun’s blog and his wonderful exploration of mathematics through Lisp. Robert Smith over at symbo1ics has a nice video on using Common Lisp for mathematics. It’s a long video that explores how Lisp is a superior platform for doing mathematics.

I’ve found this to be true in my own work. I like to experiment with cryptographic algorithms and almost always this involves bignum arithmetic. In Lisp you don’t have to think about this—it just happens automatically. If you’re writing in C it’s a nightmare. As Smith says, the code looks like assembly language where every arithmetic operation appears on a separate line.

It’s not just the numerical tower, though. Watch the video to see some of the other benefits that Lisp has to offer in Mathematical programming. Smith also covers some of the short comings of Lisp in this area.

The video is over an hour and 45 minutes so you’ll need to schedule some time to watch it. I enjoyed the video and if you like Mathematics and Lisp, you probably will too.

Posted in General | Tagged | Leave a comment

Scripting with Emacs

Sebastian Wiesner over at lunarsite has an excellent tutorial on scripting with Emacs. By “scripting with Emacs” he means we’d like to have a shell script containing some Elisp or a reference to a file containing some Elisp into which we can pass some arguments and have the script call Emacs and execute the Elisp with the arguments. It turns out to be trickier than you might think.

We all know about --script and --batch but there are a lot of corner cases that Wiesner explores. The problem, as he explains, is that Emacs is really an editor and attempts to use it as a general scripting language brings difficulties.

If you’re interested at all in scripting with Emacs, Wiesner’s post is a must read. Even if you’re not interested right now, it’s worth taking a look and bookmarking it for later.

Posted in Programming | Tagged , , | Leave a comment

The info-display-manual Command

The prolific Bozhidar Batsov has another nice Emacs tip. If you want to want to look up an Info manual and know its name you can use the info-display-manual command to go right to it. This probably doesn’t save much time unless you give it a convenient key binding—Batsov recommends 【Ctrl+i】 but you can use whatever makes sense for your configuration. If you access the Info manuals from Emacs regularly, you should head over to Emacs Redux and check out his post.

Posted in General | Tagged | 1 Comment

Emacs Rocks! Episode 15

After 19 months, Magnar Sveen is back with episode 15 of Emacs Rocks!. Emacsers everywhere will rejoice, I’m sure.

This episode is a demonstration of Pavel Kurnosov’s restclient package. It’s a very handy and simple way of exercising HTTP REST webservices. You can get results in text, JSON, XML, or even images. Watch Sveen’s excellent video to get an idea of what you can do.

Posted in General | Tagged | 2 Comments

Lisp Weenies

What’s wrong with the picture in A Cat Cons, my post from yesterday?

Posted in Programming | Tagged , | 2 Comments

The Longest Common Subsequence

Atabey Kaygun has another great post. This time it deals with finding the longest common subsequence of two sequences. First Atabey describes a simple algorithm for finding the longest common subsequence and then implements it in Common Lisp. The surprise is that it took over 4.4 seconds to calculate the longest common subsequence of the two sequences

(6 9 5 1 3 5 4 0 7 4 9 1 1 3)
(7 10 2 8 9 11 1 10 7 9 11 8 10 0 5 6 11)

The algorithm is recursive but this seems like a lot of time for a such short input. What’s going on?

Atabey gives us the answer. He memoizes his code using the code that I discussed previously. When he does this—simply using mem-defun instead to defun to define his function—the time drops to 0.006 seconds. Take a look at his lcs function and see if this surprises you. It did me. You have to think carefully about what’s going on to see why the memoization made any difference at all let alone such a dramatic one. Atabey’s post is definitely worth a read.

Speaking of memoization, if you missed PuercoPop’s comment to my previous post on the subject, be sure to follow his link to Fare Rideau’s beautiful article exploring Common Lisp implementations of the Fibonacci sequence. You’ll be glad you did.

Posted in Programming | Tagged , | Leave a comment