Now planar graphs have a dual, right? Make a vertex for every face and an edge between them if the two faces are adjacent. (Don’t forget the outer face.) Here’s a fun construction: take a spanning tree $T$ in the original graph and consider those edges impassible for the dual – that is, don’t consider the faces adjacent in the dual if the edge between them is in $T$. Call what remains of the dual graph $D$: I claim $D$ is in fact a spanning tree of the dual.…

Now today, please permit me to rant for a second about connecting the dots when you plot data. Stop it! I mean, probably. Ask yourself: “does it make sense to interpolate these data points?” The answer is probably “no” and you should just do a scatterplot with individual points. There are counterexamples: maybe you plot an ROC curve for a binary classifier. It is literally possible take linear combinations of classifiers to get the interpolated properties.…

In a previous post I talk about how NP-hardness doesn’t necessarily mean you can’t solve a problem. There are degrees to which this is true or not in practice, but there is also a distinction we can make at the level of complexity theory. Consider the KNAPSACK problem with $n$ items and maximum weight $W$. There is a famous dynamic program for this with runtime order of $n\cdot W$. That looks polynomial, isn’t Knapsack NP-hard?…

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

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