I just finished reading Programming Pearls by Jon Bentley. This is a collection of his “Programming Pearls” columns for the Communications of the ACM magazine. Bentley shares stories about implementing fundamental data structures and algorithms.
My biggest takeaway was Bentley’s authoritative yet humble tone. This stands in contrast to the high bravado and chest thumping that defines so much technical communication in the current realm of blogs and tweets. These days it seems that every writer is a gladiator who’s foremost goal is to demonstrate technical superiority. It’s king of the cage for nerds.
Bentley, a researcher at Xerox PARC, and a CMU professor who advised Charles Leiserson, is certainly a king of the technical cage. Even so, he makes you feel like he’s a coworker discussing his current project during lunch. My mind was generating imaginary suggestions for implementation techniques instead of simply digesting his word as gospel.
The columns typically highlight personalized implementation stories which often involve now antiquated machines such as the PDP-11. One personal anecdote that I really appreciated was Ed Reingold’s solution to a toy problem of searching for a missing integer. Bentley mentions that Reingold uses the question on one of his quizzes. Prof Reingold was my undergraduate advisor, and these are exactly the type of questions that he asked on his quizzes, which I always thoroughly enjoyed.
Ed Reingold said
Guilty as charged! Here is some history behind the problem.
I thought of the problem as an exam question in an algorithms course
1972; it turned out that a student in the class (Barry Finkel, now of
Argonne Labs) told the problem to his brother, Raphael Finkel, then a
CS grad student at Stanford (now at U of Kentucky). He, in turn,
mentioned it to Jon Bentley and Bentley used it in a Programming
Pearls column in CACM (at that time a real research journal) and it
was reprinted in Bentley’s book of the same name.
My wife Ruth and I were driving from Urbana to Chicago when I thought
of the problem, and it was my wife (then a grad student in chemistry
at UIUC) who had the gist of the solution that made it such a neat
problem. (The original context was from a cynical view of the Chicago
Tribune’s “Little Fooler” crossword puzzles of the 1950s.)
I always felt bad that Ruth (we’ve now been married almost 42 years!) never got
the credit she deserved.