The Design and Analysis of Computer Algorithms

What Hacker News says

1. svatApr 2021
   This is trolling, but as most of the HN comments here mention the dragon book and a careless reader may get the same impression, let me reply seriously anyway, and point out that the Turing award is not for that: https://awards.acm.org/about/2020-turing

   It is for their pioneering research work in algorithms and theory related to compilers (some of which indeed went into some of their books later). Also, even if you consider only books, they wrote nine books, and neither of the two mentioned as most influential is "the dragon book". The first mentioned is the book by Aho, Hopcraft and Ullman: Design and Analysis of Computer Algorithms (1974)

   > a classic in the field and was one of the most cited books in computer science research for more than a decade. It became the standard textbook for algorithms courses throughout the world when computer science was still an emerging field.

   This predates other major algorithms textbooks like say Kleinberg and Tardos (2005), Skiena (1st ed 1997), CLRS (1st ed 1990), or Sedgewick (1st ed 1983). Easily the standard textbook for more than a decade (and still used in some universities; it's still in print in some countries).

   > Principles of Compiler Design (1977)

   This is the "green dragon book", not to be confused with Compilers: Principles, Techniques, and Tools (1986, 2nd ed 2006) aka the "red dragon book" and the one people usually mean by "dragon book". This book is not even mentioned in the award citation. (Their automata book was widely used too.)

   So the idea that the award was given solely or even primarily for the dragon book seems entirely inaccurate. The Wikipedia pages on Aho and Ullman give some idea of their work: indexed grammars, nested-stack automata, egrep, fgrep / Aho-Corasick algorithm, the algorithms that went into yacc and lex, AWK (Aho), and "one of the founders of the field of database theory" (Ullman).

   [Edit: Shortened my very long comment.]

   Show morethread
2. ljw1001Nov 2016
   (edit) Their book, The Design and Analysis of Computer Algorithms, impressed me greatly for the clarity of the thinking and conciseness of explanation, not just compared to other algorithm books, but against anything I've read in any subject.
   thread
3. pfdietzAug 2023
   You last point there is nonsense. We can reduce division to multiplication, so we can say division is O(M(n)), where M(n) is the complexity of multiplication, even if we don't know what M(n) is. Note that big-O is an upper asymptotic bound, not an exact asymptotic bound (that's big-Theta).

   In fact, one can also show that M(n) is O(D(n)) (where D(n) is the time needed to divide n bit numbers). So they really are big-theta of each other.

   (See Aho, Hopcroft, and Ullman, The Design and Analysis of Computer Algorithms, 1976, section 8.2)

   Show morethread
4. jefffosterNov 2010
   They are both algorithm books and the initials are the last names of the authors.

   AHU is "The Design and Analysis of Computer Algorithms" by Aho, Hopcroft and Ullman.

   CLR is "Introduction to Algorithms" by Cormen, Leiserson and Rivest

   thread