Electronic Computing is Janky AF


Now there’s this funny type of project, right, where somebody does computation with something that’s not “for” computing. Using marbles in some kind of pachinko rig to add binary numbers. Pinging slow servers to temporarily store data.1 I guess redstone in Minecraft kind of is for making circuits, but people have built like … Turing machines and that’s funny. It’s all a bit janky and there’s an absurdist humour to it: these are high-effort shitposts.…
Read more ⟶

How to Describe a Dynamic Program in a Paper


Now today I’d like to talk about a bit of a pet peeve of mine and I guess it’s maybe more of an opinion than usual, or at least it’s something stylistic: how to describe a dynamic program. Sometimes people immediately come at you with a table and how you would loop over it; where to look and what to write – and, I mean, it’s not wrong. If you describe this well, I’ll understand it.…
Read more ⟶

Courcelle's Theorem and Monadic Second Order Logic (MSO)


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.…
Read more ⟶

Software for Making Plots


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?…
Read more ⟶

Python's http.server


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.…
Read more ⟶