# Dual Spanning Trees in a Planar Graph

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

Read more ⟶
# Don't Connect the Data Points on your Scatterplots

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

Read more ⟶
# Strong and Weak NP-Hardness

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

Read more ⟶
# 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 ⟶