Counting Spanning Trees

Posted on 2014-11-13 by jcs

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 \[l_{ij} = \begin{cases} \text{deg}(i) & \text{if } i=j,\\ -1 & \text{if there is an edge between } i \text{ and } j,\\ 0 & \text{otherwise}. \end{cases}\]

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.

Posted in General | Tagged , | Leave a comment

Org Mode and Reproducible Research

Posted on 2014-11-12 by jcs

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.

Posted in General | Tagged , | Leave a comment

Emacs on Git

Posted on 2014-11-11 by jcs

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

IE on Mac

Posted on 2014-11-10 by jcs

Why?

Posted in General | Tagged | Leave a comment

Building gnuplot on OS X

Posted on 2014-11-10 by jcs

As part of my on-going efforts to get my new MacBook Pro set up with my normal working environment, I tried to compile gnuplot. The first problem was that libpng and libgd were not installed so there was no png support. In short order, I downloaded the libraries and got them compiled. On to building gnuplot.

The problem was that the configure script for gnuplot could not verify that libgd was installed even though it was. I tried all sorts configure arguments and other machinations but no joy.

I asked DuckDuckGo and it said that everyone was having the same problem but none of the suggested solutions worked. Finally, I gave up and just modified to configure script to believe that it had found it. configure scripts are notoriously opaque and very hard to figure out. After a bit of fussing around, I got it to believe that libgd really was there. After that, gnuplot compiled with png support and works perfectly.

I think this is probably some artifact of Apple using LLVM instead of gcc. If you’re trying to build gnuport on a recent version of OS X and having problems with libgd support, here’s a patch for configure that worked for me. 

--- configure.orig      2014-10-19 08:18:04.000000000 -0400
+++ configure   2014-10-19 08:46:47.000000000 -0400
@@ -10266,7 +10266,9 @@
 else
          { $as_echo "$as_me:${as_lineno-$LINENO}: WARNING: libgd not found or too old, version >= 2.0 is required" >&5
 $as_echo "$as_me: WARNING: libgd not found or too old, version >= 2.0 is required" >&2;}
-       with_gd=no
+       with_gd=yes
+$as_echo "#define HAVE_GD_PNG 1" >>confdefs.h
+libgd_LIBS="$libgd_LIBS -lpng"

 fi

@@ -15456,7 +15458,8 @@
 fi


-if test "$ac_cv_lib_gd_gdImagePng" = yes; then
+#if test "$ac_cv_lib_gd_gdImagePng" = yes; then
+if true; then
   { $as_echo "$as_me:${as_lineno-$LINENO}: result:   png terminal: yes" >&5
 $as_echo "  png terminal: yes" >&6; }
 else

This is probably not an optimal patch since I was flailing around trying to get it to work but it is, after all, just to get configure to agree that libgd is there. Just make sure that libgd really is installed.

Posted in General | Tagged , | Leave a comment

Join the NSA and Do Illegal Things

Posted on 2014-11-09 by jcs

You probably can’t legally do those things at the NSA either. It’s just that you likely won’t get caught.

Posted in General | Tagged | Leave a comment

Rating Secure Messaging Applications

Posted on 2014-11-09 by jcs

The EFF has published its Secure Messaging Scorecard that rates several messaging applications on several important security axes. Some have all the desired attributes, others have none. Some, like Apple’s iMessage have most of the attributes but fail to be open source or have the ability to verify a contact’s identity.

The EFF says this is just an overview and that they are working on additional, deeper analyses of the usability and security of the tools that scored best in this initial phase. As the EFF says, this scorecard is not an endorsement or guarantee, just an indication of which of the applications are on the right track.

I’m looking forward to the future reports. I consider iMessage reasonably secure for day-to-day use but if I had something I really needed to be sure was secure, it would be nice to have some help choosing the best tool.

If you have any interest in secure messaging, you should take a look at the score card. And, of course, though I haven’t said so for a while, you should help support the EFF. They are working to protect us all.

Posted in General | Tagged | Leave a comment

Microsoft

Posted on 2014-11-08 by jcs

Still evil after all these years.

Posted in General | Tagged | Leave a comment

Genes Best Removed from the Pool

Posted on 2014-11-08 by jcs

Yikes! Who would do this? No Irreal readers, I’m certain. Worse, all these instructions appear to be aimed at developers who should surely know better. I especially like the ones with sudo. Really, if you enter one of those commands into your terminal, don’t be surprised to find your genes excised from the pool.

And what’s up with companies recommending this nonsense? I can promise you that the first time I got that from a company I deal with, it would be the last time I dealt with them. It’s a sure indication that the company knows nothing about security and doesn’t care to learn. It’s also an indication that they don’t really care about their customers because if they did, they wouldn’t be training them to compromise their systems.

Posted in General | Tagged | Leave a comment

Dowsing

Posted on 2014-11-07 by jcs

Wilfred Hughes makes an acute observation:

Sometimes, it does seem like that.

Posted in General | Tagged | Leave a comment