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

## A Cat Cons

Via Magnar Sveen we have this offering from Dmitry Ignatiev

## Sharp Quote and Emacs

Artur Malabarba has some good advice on sharp quoting Elisp functions. It's common for Elisp programmers to use a single quote (i.e the quote form) to mark functions. Malabarba explains why it's better practice to use #' (i.e. the function form) to indicate a function.

This is a great post (as usual for Malabarba) and all Elisp programmers should read it.

## Amazon and the Publishers

Over at Vox.com, Matthew Yglesias has a provocative article on the contretemps between Amazon and the publishing industry and with Hachette in particular. It's mainly been portrayed in the press as an argument over prices but Yglesias says that's just a side show.

The truth, he says, is that the publishing industry is dying and its current battles with Amazon won't alter that fact regardless of the final outcome. The reason for the industry's imminent death is that it no longer provides any benefit.

That wasn't always true, of course. It used to be that books had to be typeset, printed, bound, and shipped to retailers. It was virtually impossible for authors to do these things on their own so the publishers provided a necessary service. With the advent of ebooks, those services are no longer required. Software to take an author's manuscript and produce an ebook is widely available, often for free. And, of course, printing, binding, and shipping are not required at all.

What about marketing, then? Surely one of the key services a publisher provides the author is marketing. Yglesias says that, in fact, the publishers are terrible at marketing. He says that the current argument between Amazon and Hachette proves this. If Hachette actually was good at marketing they could simply market their books to other vendors and directly to the public at large.

You may or may not agree with Yglesias but one thing he says is certainly true: the fight between Amazon and Hachette really boils down to who gets to keep the extra profits flowing from the fact that producing another copy of an ebook is essentially cost free. Amazon says they should be used to reduce the price. Hachette wants to keep them. Inasmuch as Hachette and the other publishers have been claiming for years that ebooks cost about the same as physical books to produce, I'm not inclined to accept their arguments.

Yglesias has other arguments supporting his thesis so you should definitely go read what he has to say. It's a fascinating idea you don't hear very often—at least in public.

## Being Smart

Matt Blaze has a realization that probably applies to us all. I know it applies to me.

## Day of the Year

This is really a note to myself. The other day I needed to figure out what day of the year it was. I was pretty sure that the Unix date command could tell me but I couldn't remember how to do it and it wasn't clear from the manual. It turns out the answer is there but not obvious.

The first thing to know is that a starting character of + in the argument tells date that a custom display string is coming. In that string you can use any of the strftime options. One of those is %j for the Julian day of the year. Thus, the answer is simply

date +%j


which for today gives

319


## Using Emacs and Org Mode for a Journal

Howard Abrams has an excellent post on journaling with Emacs and Org Mode. The post documents how his use of Org Mode evolved over time so you can see what (at least for him) worked and didn't work. That's very useful for figuring out your own strategy even if you settle on something different from what he did.

One of the things I like about his approach is that he uses org-capture to make his entries. That's nice because no matter what you're doing you can pop up a capture buffer, make a quick entry, and go back to what you were doing with very little effort. That makes it easier to maintain the journal because it's almost frictionless.

Another nice thing I learned from his post is autoinsert. It allows you to automatically insert text to the start of a file when you first create it. It's another in the long list of ways that Emacs can make your workflow more frictionless.

Even if you're not interested in maintaining a journal, you should give this post a read. You may learn a useful technique or two.

## Counting Spanning Trees

I really enjoy Atabey Kaygun's blog. If you like Mathematics and Lisp, you're sure to enjoy it too. A typical post looks at a mathematical problem and either presents a solution or experiments with the problem with Common Lisp.

One of his recent posts considers spanning trees (ST) and how to count them. Most of us—at least those who have taken an algorithms course—are familiar with the simple construction to find an ST but may not know how to count them.

Atabey introduces the notion of the Laplacian of a graph, $L$, defined by

Kirchhoff's theorem tells us that the number of spanning trees is equal to any of the minor determinants of the Laplacian. This is a pretty neat result and one that I didn't know. Atabey's post has a couple of worked examples and Lisp code to make the calculations.

As I said, if you like Mathematics and enjoy programming in Lisp, you should definitely give this post a read.

## Org Mode and Reproducible Research

EmacsNYC has another great video up. This time, its Evan Misshula talking about Org-mode and reproducible research. Misshula is a graduate student in Criminal Justice at CUNY who does a lot of statistical research on Criminal Justice matters.

Like me, he's a big advocate of reproducible research and spends much of his presentation talking about how Org-mode can facilitate that. In the first part of the talk he explains why reproducible research is so important. If you're any kind of scientist, the statistics that he gives will set your hair on fire.

As a result of the high error rate with research that is not reproducible, Misshula refuses to review or cite any papers that aren't reproducible and he urges other researchers to do the same. As I said, the statistics for research that is not reproducible is staggering. Sadly, this applies to Computer Science as much as it does to other disciplines. Watch the video to learn the details.

## Emacs on Git

It's been a long time coming but as of today, Git will be the official repository for Emacs. It's easy to miss what a monumental achievement this is.

It would be easy to shrug off the news with a so what. Move the files over to Git and be done with it. It turns out to be way, way harder than that. Eric Raymond (esr) has spent most of the last year making the transition. That's more amazing when you realize that esr is probably the world's leading expert on moving repositories to Git.

Emacs is about 30 years old and has been hosted on several VCS systems. Here's a post by esr that describes some of the problems he had to deal with. Elsewhere he remarks

You might think “Huh? Emacs already has a git mirror. What else needs to be done?” Quite a lot, actually, starting with lifting Bazaar commit references into a form that will still make sense in a git log listing. Read the recent emacs-devel list archives if you’re really curious.

Along the way, he's also transferred other large repositories, including Groff, and has looked at doing the same for the NetBSD codebase. He's also developed several tools, such as reposurgeon and cvs-fast-export. Search his blog for either of those two terms to get an idea of the huge amount of effort he's expended just in engineering the tools.

We all owe esr a debt of gratitude for the yeoman service he's put in on this project and on migrating other code bases to Git. Well done, sir.

UPDATE: esr is reporting that the new repository is on-line and available for cloning at git://git.sv.gnu.org/emacs.git.

Posted in General | Tagged | 4 Comments