Thore Husfeldt

I am back from sunny Zürich and ICALP 2011.

This was a very well-organised event hosted at ETH. Michael Hoffmann had everything under complete control and remained confident, alert, calm and accessible. I’ve tried go take a glimpse behind the curtains, such as looking at the two-page to-do list for technical staff in the lecture halls, and the level of detail and relevance is just off the scale. I hope Michael can summarise his preparation and tips for everybody’s benefit.

Future Publication of the ICALP Proceedings

The EATCS general assembly is by tradition a long and dry event without free beer. To break new ground, the organisers handed out free ice cream. ’tis not beer, but a welcome step in the right direction. I hope the organisers of next year’s ICALP, Warwick, take note.

Burkhard Monien’s EATCS Annual report 2010-2011 [PDF] is available on-line, so there’s no need to summarise it here.

The exciting question is the publication model for ICALP: will the EATCS flagship conference stay with Springer’s LCNS series (or some transformation of it) or not? I blogged about this last year, from the 2010 assembly:

Monien explained the EATCS council wants to get this right, ICALP is a big steamer, should not go in zig-zag course, and stick to its decisions. He was unsure if the next poll will be implemented in the Fall, but promised “beginning of next year, at the latest.” I’m not holding my breath.

Well, the Fall of 2010 has come and gone. The EATCS council had another meeting during ICALP 2011, and Monien summarised the decision. Here’s what I was able to jot down quickly from his presentation:

• The decision is between Springer and the LIPIcs series and will be decided by the members of EATCS by a ballot “at the end of the summer.”
• The EATCS Council recommends to go with Springer.
• The poll will include the following documents: The proposals from both Springer and LIPIcs. The recommendation of the EATCS council. A dissenting opinion from a minority in the Council. A list of pros and cons.
• The final decision is made by simple majority among EATCS members. A quorum of 25% is necessary.

For a quick calculation, the report currently lists 787 EATCS members. So some 200 members would need to respond. Get out the vote!

As a sign that times are changing, the ICALP proceedings were online and digitally available to all conference attendees at the time of the conference. Splendid.

Name Tags

I obsess about name tags.

ICALP 2011 chose the neck band solution, which I derided in a brilliant piece of investigative journalism Post ALGO 2009.

In the comments of that post, G. Philip suggested to print names on both sides of the tag, so as to increase the probability of legibility close to 1. Remarkably, this was exactly what the organisers had done!

(Again, enterprising conference attendees managed to defeat the good intentions. The lunch tickets happened to fit exactly in the name tag pocket, so that with probability close to 1/2, the tag showed the name badge, and with probability close to 1/2, it showed lunch tickets. Incidentally, lunch tickets also had your name on them, but only printed on one side. Thus, in total, attendees were identifiable with probability around 3/4.)

But the big problem with neck bands is that the name badge ends up below table height during lunch and also otherwise is awkward to inspect.

The layout of the ICALP 2011 badge is fair. A good part of the real estate is actually taken up by the attendee’s name. Also, accents were correct as far as I could tell.

In fact, the organisers chose to display first names in larger size, giving the event a friendly touch. I like this. However, during a thoughtful lunch conversation, somebody (I don’t know who because his name tag was dangling below the table) mentioned that the last name is more useful for striking up conversations. Especially newcomers would prefer to know that they’re talking to Turing instead of Alan.

I’m undecided about the name size issue. Maybe another EATCS poll can decide it.

The list of accepted papers for ESA 2011 is online. Below is my own quick take on which papers are about exponential time algorithms.

ESA 2011 is colocated with IPEC under the ALGO 2011 umbrella, so there will be plenty of exciting results that week.

• Dimitrios Thilikos. Fast sub-exponential Algorithms and Compactness in Planar Graphs.
• Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, Stéphan Thomassé, Hitting and Harvesting Pumpkins, arXiv:1105.2704.
• Fedor Fomin, Ioan Todinca and Yngve Villanger, Exact algorithm for the maximum induced planar subgraph problem, Todinca’s slides from Worksh. Graph. Decomp. 2010.
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk, Scheduling partially ordered jobs faster than 2ⁿ.

I’m probably missing some results, but without online abstracts it’s hard to tell. I cannot judge a paper from its title alone. Comments and corrections are welcome, in particular links to online manuscripts.

I managed to excite Danish weekly Weekendavisen about the societal impacts of internet personalisation, along the lines of Eli Pariser’s recent book The Filter Bubble. This resulted in a nice, meaty two page article starting on the front page of the paper’s science section Idéer.

This is part of my ongoing effort to unleash the meme of the Algorithmic Lens in the public discourse. Two years ago I initiated an article about the algorithmic lens on the sciences in the same paper.

The Social Science Filter Bubble

The creation of such an article is a give-and-take between me and the journalist. I’d collaborated with him previously on the production of a TV programme about how Google’s page rank algorithm works, so we had established a level of common trust. Still, we come from vastly different epistemological backgrounds.

Here’s a detail that made me smile.

I originally suggested a formulation along the following lines:

Dewey and Habermas are fine, but today the public sphere is shaped by algorithmic processes, and we’re just in the beginning of that development. And just like we turn to Newton to understand gravity, we must turn to Turing and his disciples to understand some of the forces that influence the behaviour of individuals and groups in the information society.

Plenty of dropped names, and it was rejected for being too opaque. Consequently, in the final version, the references to philosophers Dewey and Habermas remain, but Newton and Turing have been removed. So, the readership of Weekendavisen is of course expected to know the public sphere and the civil society (as rightly they should). But they are protected from having to google who the other two guys are.

This is an example of the “old” filter bubble, where media through self-selection and editorial policy shape a common frame of reference, an understanding of what a Citizen is supposed to educate herself about.

In the Brave New World to come, an algorithm would have processed my quote. It would perhaps have replaced “Dewey and Habermas” by “Philosophers” or “Some social scientists” or “Dead White Males” on a per-reader basis, based on the epistemological priors, background knowledge, and ideological preferences of the reader.

Further reading

If you came here from Weekendavisen because you googled my name – provided your personalisation settings allowed me to burst your filter bubble –, and want to read more, check out thefilterbubble.com. That’s Eli Pariser’s blog, including links to his book, his TED talk video, and a list of 10 ways to pop your filter bubble.

Alternatively, check out my recent (Danish) TV production How Google works, which explains the PageRank algorithm. Now, the Good Olde Days.

Or you can hire me to give a talk; I have several ready, such as Hvordan Google virker or The Algorithmic Lens. See the full list at Popular Science talks.

Update: I also appeared on Danish public radio about this: P1 Morgen 4 Jun 2011, 7m45s, around 9:30.

Update: And even the the local paper Sydsvenskan: De digitala skygglapparna (4 July 2011) (in Swedish).

Update: And even in Svenska Dagbladet:
Isolerade i nätbubblan (15 August 2011) (in Swedish).

Image source: Wikimedia Commons

I keep most of my LaTeX source files under the revision control system Git.

Git is opinionated software. It allows you to do many things, but others run counter to its dogmas. In particular, Git does not modify source files.

Other systems do. For example, you can ask Subversion to replace the placeholder $Revision in the committed source file with the latest revision number. This is useful for displaying revision numbers or dates in your LaTeX documents, for example.

From Git’s perspective, modification of source file is pure evil. Not only is this feature absent from Git, but the very request betokens moral corruption.

From Git’s perspective, the client programme (in this case, LaTeX) is responsible for including revision information in the output. Git humbly makes that information available. But it does not modify the source.

Stephan Hennig’s vc bundle consists of a number of scripts that extract revision information from various version control systems, including Git, and make it available as LaTeX macros. The information is taken from a separate, automatically generated input file vc.tex, so that the main LaTeX source file remains untouched by Git.

This shifts the problem to the generation of vc.tex. I’ve played around with various solutions based on Makefiles, and here is my current setup.

The vc.tex file is automatically generated and defines three LaTeX macros. Typically, it looks like this:

%%% This file is generated by Makefile.
%%% Do not edit this file!
%%%
\gdef\GITAbrHash{f61c739}
\gdef\GITAuthorDate{Fri May 13 10:34:51 2011 +0200}
\gdef\GITAuthorName{Thore Husfeldt}

The main LaTeX source includes the vc.tex file in the preamble and can now freely use these macros. For example, the revision information can be included in a footnote on the title page.

\documentclass{article}
...
\input{vc.tex}
...
\begin{document}
\maketitle
\let\thefootnote\relax
\footnotetext{Base revision~\GITAbrHash, \GITAuthorDate, \GITAuthorName.}
...

The responsibility of producing an up-to-date vc.tex rests on the Makefile:

latexfile = main

all: $(latexfile).pdf

$(latexfile).pdf : $(latexfile).tex vc.tex
	while (pdflatex $(latexfile) ; \
	grep -q "Rerun to get cross" $(latexfile).log ) do true ; \
	done

vc.tex: .git/logs/HEAD
	echo "%%% This file is generated by Makefile." > vc.tex
	echo "%%% Do not edit this file!\n%%%" >> vc.tex
	git log -1 --format="format:\
		\\gdef\\GITAbrHash{%h}\
		\\gdef\\GITAuthorDate{%ad}\
		\\gdef\\GITAuthorName{%an}" >> vc.tex

The interesting rule is the last one. It runs git log to produce vc.code. The hardest thing for me was to get the dependencies right. I think I’ve got it now. The input file vc.tex needs to be regenerated whenever it predates the last commit. As far as I understand the Git internals, the modification time of .git/logs/HEAD should give me a reliable timestamp for when the last commit happened, so I made my rule for vc.tex depend on that.

Of course, it’s a cheap operation, so we could generate vc.tex anew every time we run pdflatex. But then every call to make would recompile the source (because vc.tex has changed). To avoid that, we could leave vc.tex out of the dependencies for $(latexfile).pdf. But then a commit (which modifies the revision number but not any source files) would not lead to an automatic recompile. The LaTeX document would only display new revision information whenever it is edited after that revision.

If there’s a cleaner way of checking for “is vc.tex outdated compared to the Git repository”, please tell me.

TODO: Make the LaTeX document reflect that it corresponds to uncommitted edits after the latest revision. This should be doable by comparing the modification times of the LaTeX source files and .git/logs/HEAD. A cruder way is to let git status tell the Makefile if working directory is “clean”.

UPDATE (21 Feb 2012): Since this post was written, various other approaches have appeared. (Thanks to the commenters for pointing them out.) The idea of using a post-commit hook instead of a Makefile is now on CTAN: gitinfo package.

I teach generation Z, people who are now in their early twenties.

Generation Z follows Generation Y, which follows Generation X.

What will we call the next generation? We’ve run out of letters! “Generation [”?

Well, it doesn’t matter. Read on…

I was reviewing old exam questions in my introductory algorithms and data structures class. Here’s the question:

This looks innocent enough. However, several students were openly annoyed by this question.

What’s the problem? It has nothing to do with priority queues or heap order or anything else algorithmic. If you aren’t generation Z, you’ll never guess.

They asked me to please use numbers instead of letters. Why? I turns out that comparison between letters is no longer constant time! As one student put it, with a straight face, it’s really hard to determine if, say, Q is higher or lower than some other letter. Helpful students sagely suggested to their fellow students to just start by making a list of the alphabet on a separate piece of paper for this type of exercise. This was met with earnest nodding.

It was quite clear that I had made this question needlessly difficult by making it about letters.

This is a sterling example of a skill that is utterly natural to my generation, who has looked things up alphabetically countless times. I have no harder time comparing M and S than I have comparing 5 and 13. But, of course, Generation Z has never looked anything up alphabetically. It‘s an utterly useless skill honed in the olden days of outdated information technology, like knowing how a slide rule works or typing on a T9 mobile phone keypad. Generation Z finds this as hard (and as useless) as I find it comparing Ψ and Φ. I can do it, because I memorised the Greek alphabet with I was eight or so, and can still rattle it off in the right order. But it takes linear time in the size of the alphabet.

So, from now on, I guess I use plain old numbers in this type of exam questions.

Also, the generations following Generation Z can be safely called Generation W, V, U, etc. Nobody will notice.

Also, I feel old.

The accepted papers for ICALP 2011 have been announced.

Based on my quick perusal of the track A papers with abstracts, here’s a list of papers related to exponential time computation, together with references to online version — I’m probably missing some.

• Isolde Adler, Stavros Kolliopoulos, Philipp Klaus Krause, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos. Tight Bounds for Linkages in Planar Graphs. PDF at Adler’s web page.
• Sanjeev Arora and Rong Ge. New Algorithms for Learning in Presence of Errors. PDF at Ge’s web page
• Hans L. Bodlaender, Bart M. P. Jansen and Stefan Kratsch. Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization. arxiv:1104.4217.
• Andrei Bulatov and Dániel Marx. Constraint satisfaction parameterized by solution size.
• Amin Coja-Oghlan and Angelica Pachon-Pinzon. The decimation process in random k-SAT. arxiv:1102.3145
• Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk and Jakub Wojtaszczyk. Subset Feedback Vertex Set is Fixed Parameter Tractable. arxiv:1004.2972.
• Daniel Lokshtanov and Dániel Marx. Clustering with Local Restrictions. PDF at Lokshtanov’s web page.
• Danny Hermelin, Matthias Mnich, Erik Jan Van Leeuwen and Gerhard J. Woeginger. Domination when the Stars Are Out. arxiv:1012.0012

Unfortunately, nothing about ETH. That would have been fun.

This post in Danish.

Formålet med denne oversigt er at sammenfatte (og til en vis grad foreslå) dansk fagterminologi for algoritmer og datastrukturer. Movitationen er dels at lette oversættelsen af fagtermer både mellem og inden for begge sprog, dels at stille dansk terminologi til rådighed for dem, der måtte have behov for at udtrykke sig skriftligt eller i formidlingsøjemed uden for snævre fagkrede.

Blandt fagfæller vil man i de fleste mundtlige situationer kunne gøre sig bedst forståelig ved at anvende de engelske termer med tillempet dansk-engelsk udtale og syntaks (»til sidst merger du /arraysene/«). Denne tilgang kan også anbefales, hvis man primært er interesseret i at signalere tilhørighed til fagfællesskabet.

Jeg har stor sympati for den angelsaksiske tradition for at finde fagtermer som er både kødfulde og ofte lidt latterlige (mouse, bubble sort, stack), dels fordi det skaber nyttige analogier i en ellers fremmedgørende digital virkelighed, dels fordi uhøjtideligheden nedbryder den benovelse, men ellers kan føle i mødet med fagterminologi. Desværre går begge disse effekter tabt, når mindre gængse engelske ord (merge, browse, hash, array) bruges uoversatte.

Der findes mig bekendt intet trykt dansksproget material i algoritmer og datastrukturer ud over Schmidt og Scharzbachs noter »Programmeringsteori og datastrukturer« og »Grafalgoritmer og algoritmisk problemløsningsteknik« fra Aarhus Universitet fra 1990erne og Polyteknisk forlags »Find formlen – algoritmer og datastrukturer« fra 2007. Deres terminologi er medtaget her. Jeg er taknemmelig for
at blive gjort opmærksom på dokumenterede forekomster af ord jeg måtte have overset. Nogle af konstruktionerne forneden er dog helt mine egne forslag; jeg har markeret dem med et advarende udråbstegn.