December 23, 2025
CC’d the Algorithm Avengers
Correspondence Between Don Knuth and Peter van Emde Boas on Priority Deques 1977 [pdf]
Vintage algorithm letters hit the web, and the CC list + furniture jokes run wild
TLDR: Historic 1977 letters from Donald Knuth and Peter van Emde Boas explaining a “priority deque” just hit the web. Comments fixated on the celebrity CC list (Hopcroft, Tarjan) and furniture/pronunciation jokes, splitting readers between algorithm history fans and “just use modern tools” pragmatists.
A dusty pair of 1977 letters just resurfaced: a back‑and‑forth between legend Donald Knuth and Peter van Emde Boas about “priority deques”—think a VIP to‑do list where you can add and remove items from both ends. The docs include the origin of Knuth’s famous correctness quip and the first modern, top‑down way to explain this data trick. Also in the chat: a throwback debate about whether using multiplication in a classic “RAM model” (old‑school rules for how long computer steps take) is fair game.
But the community didn’t read quietly—they reacted like it was a red‑carpet drop. User jibal immediately spotlighted the CC line, name‑dropping algorithm A‑listers John Hopcroft and Robert Tarjan. Cue the memes: academic Avengers assembled. Then brap lobbed the ultimate deadpan, “What was the piece of furniture?” igniting the eternal deque pronunciation war (is it “deck” like a patio? “de‑queue” like a line?).
Strongest opinions? History buffs swooned over the archival tea and the recursive elegance; pragmatists joked they’d just use modern library tools and skip the vintage math drama. The disagreements were playful but real: did those old constraints even matter, and why are we still arguing about how to say “deque”? In short, the document is brainy—but the CC list and furniture jokes totally stole the show.
Key Points
- •A 1977 Knuth–van Emde Boas correspondence on priority deques has been made accessible online as a facsimile.
- •The document provides the first top-down recursive description of priority deques, now a common presentation.
- •Original publications avoided the recursive approach due to reliance on multiplicative instructions considered inadmissible under the uniform-time RAM model.
- •The facsimile includes Knuth’s cover letter, van Emde Boas’s reply, and references to key works from 1974–1977.
- •A 2013 paper by van Emde Boas offers extended historical context on stratified trees, referenced by the article.