Now there are all kinds of so-called “meta-theorems” that connect logic and graph algorithms. Here’s a pretty cool one using a logic you may not have heard of: the monadic second-order logic of graphs. You see, Courcelle’s theorem says that for graphs of bounded treewidth, properties definable in this “MSO” logic can be decided in linear time. This makes the graph problem fixed parameter tractable parameterized by treewidth. The proof involves some fairly heavy machinery (or at least terminology I’m not super familiar with) so I personally find the primary literature quite hard to follow and you do have to be a little bit careful what the exact conditions are if you’re going to use it for real, but you know the drill: look it up.…

Now in my first journal paper (and this is back when you would get author’s copies, I still have a stack of like 20 of these; you could send them to colleagues, I guess) the plots were EPS exported from Excel. While it was an upgrade from the screenshots I took for my thesis, it doesn’t look great either way. So how do you make plots and graphics for your papers?…

Now you might want to hack something together to run in the browser – I have this Fréchet distance visualisation, for example, that I wanted to run on a tablet and this seemed to be the easiest way to go. But then if you’re developing this locally, your JavaScript can’t read any files because, like, this is javascript in the browser and it shouldn’t be reading your files. And even if the files are on a server somewhere you get into cross site scripting shenanigans, so you really kind of need to serve things over HTTP for real.…

Now I like to say that computer science is not about computers. That it’s kind of a historical accident of the English language that it’s even called that. I much prefer the Dutch informatica, but that’s neither here nor there. My compatriot Edsger Dijkstra reportedly put it like this: computer science is no more about computers than astronomy is about telescopes. As in: yes, we use computers – and we have opinions about them – but that’s not what we’re actually studying.…

Now let’s talk about an error you might get from a compiler that can be confusing at first, but it makes sense once you think about it. (That’s usually how it is with compile errors, right?) Question: If I have a function that takes a List<Animal> as argument, should I be able to pass it a List<Cat>? Uh, that depends on the programming language, as it turns out – but let’s think about it in the spirit of Barbara Liskov’s “substitution principle:” if something has to be an Animal and it turns out it’s actually a Cat, that should be fine almost by definition: instances of the subclass are acceptable where the superclass is expected.…