-
Ready lists
Beginning computer science students learn about stacks, queues, and priority queues, different ways of organizing and ordering a collection of tasks to be performed. But more basic than any of those, and less frequently taught and formalized, is the ready list, a collection of tasks to be performed whose ordering is not important. All it needs to do is to allow new tasks to be added to the collection and to find and remove an arbitrary task from the collection.
-
Geometric street art in Kanazawa
Kanazawa was this year’s host of Computational Geometry Week and the Symposium on Computational Geometry, and a great place to visit for lots of reasons. One of the lesser reasons is that it also hosts an interesting collection of geometric street art, some of which I photographed on my recent visit.
-
Linkage
- Robin Houston dissects the outer shell of a \(4\times 4\times 4\) polycube into seven interlocked pieces, picking up from a 2023 discussion where I found a six-piece solution. With bonus short video by George Miller showing that, with round enough cubes, it makes a nice snap-together puzzle.
-
Linkage with pelicans
- ViXra launches archive of AI-generated papers (\(\mathbb{M}\)). In case your daily dose of crankpottery needed supercharging.
-
Two recent preprints
I have two new(ish) arXiv preprints that I thought I would announce together here rather than devoting a separate post to each of them.
-
Linkage
- Anti-inductive dice (\(\mathbb{M}\)). One player rolling \(n\) copies of one die is more likely to win than the other player rolling \(n\) copies of the other die, except when \(n=4\).
-
Bandwidth vs breadth-first search
Another new preprint of mine recently appeared: “Bandwidth vs BFS width in matrix reordering, graph reconstruction, and graph drawing”, arXiv:2505.10789, with Mike Goodrich and his student Alfred Liu. For me, it started with a mistake.
-
Linkage
- Nature on National Science Foundation terminating hundreds of grants and planning for massive budget cuts (\(\mathbb{M}\)). Terence Tao writes “this is going to be hugely disruptive … and in conflict with the congressional authorization of funds appropriated for the NSF”.
-
Turnstile majority
A famous algorithm of Boyer and Moore for the majority problem finds a majority element in a stream of elements while storing only two values, a single tentative majority element \(m\) and a counter \(c\). Every time it seems a stream value equal to \(m\), it increments the counter, and every time it sees an unequal element, it decrements the counter. If this would cause the counter to go negative, it replaces \(m\) by the value that it sees and resets the counter to one. At the end of the algorithm, if there is any element that repeats for more than half of the items in the stream, then that element will be the one stored in \(m\). But otherwise, the result of the algorithm is undefined. Here’s a visualization I made of the algorithm for its Wikipedia article, with the data stream running across the bottom, the height of the graph showing the stored counter, and the icons on the graph showing the stored stream value:
-
Why I linkage
- Archaeologists claim intellectual property rights to ancient Roman dodecahedra (\(\mathbb{M}\), via), dozens of which exist in multiple museums, and block online sales of replicas. According to Wikipedia there are “more than fifty possible explanations” for what these things might have been used for.
subscribe via RSS