-
Linkage
-
The degree of Fibonacci heaps
The Fibonacci heap is a priority queue data structure in which finding and removing the top-priority item takes logarithmic time (like a binary heap) but reprioritizing items to have higher priority takes only constant time, under amortized time analysis. This property is useful for speeding up the time complexity of algorithms including Dijkstra’s algorithm for shortest paths and Jarník’s algorithm for minimum spanning trees, so that they take logarithmic time per vertex and constant time per edge.
-
Linkage
-
Cubic salespeople revisited
Good news: Email from Knuth. Bad news: It begins “is there a bug in your paper?” The paper in question is “The traveling salesman problem for cubic graphs” (WADS 2003 and JGAA 2007). Of course the bug report is accurate, but fortunately it can be easily patched.
-
Linkage
-
H-trees are not trees
A sheet of a4 paper has aspect ratio \(1:\sqrt2\). This means you can crease it along the shorter of its two midlines to get two rectangles with the same aspect ratio (of a5 size) and continue in the same way recursively.
-
Linkage
-
Linkage with plum blossoms
- Remembering Joe Halpern (\(\mathbb{M}\)) focuses on Joe’s pivotal role in founding and guiding the CS section of the arXiv.
-
Making accessible LaTeX talk slides with ltx-talk
US-based academics are being required by the government and by their universities to make all online content accessible by April 24, and I think many of us have been running around trying to figure out what that means and how to do it. My university has been especially unhelpful, demanding compliance in vague terms but not telling us what standard they’re using and pointing only to Microsoft and Google’s web sites for guidance on how to improve accessibility for Microsoft and Google products. The relevant standard appears from the government links to be WCAG 2.1 AA. For those of us who have been using the LaTeX beamer package to create mathematical course lecture notes as pdf files, beamer cannot do this. The accessibility standards require tagged pdf and beamer does not have code to generate the tags correctly. But there is a solution: a replacement package, ltx-talk, that is mostly compatible with beamer. After some effort, I have succeeded in using ltx-talk to create slide decks that closely resemble my old beamer decks both in appearance and coding and that pass all automated accessibility checks in Acrobat. That makes now a good time to record what I have learned about going from beamer to accessible ltx-talk, before I forget it all again.
-
Linkage
- Joe Halpern (1953–2026) (\(\mathbb{M}\)). A leader in the mathematical reasoning about knowledge, founder of the Computing Research Repository (later the CS branch of arXiv), and recipient of the Gödel Prize and Dijkstra Prize.
subscribe via RSS