Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!cs.utexas.edu!ut-emx!plyon From: plyon@ut-emx.uucp (Paul Lyon) Newsgroups: comp.lang.misc Subject: Re: Will this *thread* ever halt? Message-ID: <51083@ut-emx.uucp> Date: 24 Jun 91 01:21:47 GMT References: <29254.Jun2219.22.4491@kramden.acf.nyu.edu> <12358.Jun2400.03.5891@kramden.acf.nyu.edu> Organization: The University of Texas at Austin; Austin, Texas Lines: 26 In article <12358.Jun2400.03.5891@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article oz@ursa.ccs.yorku.ca (Ozan Yigit) writes: > [ on Knuth's Art of Computer Programming ] >> Those volumes are not out of favor, but they are out-of-date by a >> decade and a half, > >Really? Within the subject matter covered by volumes 1 through 3, can >you name any important algorithm (i.e., algorithm used by a significant >percentage of today's programmers) not mentioned by Knuth? It strikes me that there are some obvious examples here, some of which Knuth himself had a hand in discovering. For example: the Knuth-Morris- Pratt string searching algorithm and the Knuth-Bendix completion algorithm for term-rewriting systems (the basis for a good deal of the activity in "Logic Programming" relating to equations). Other obvious examples are the Boyer-Moore string searching algorithm and the Simplex algorithm. Then there is Robinson's Unification Algorithm, the alpha-beta minimax algorithm, and so it goes.. For, bear in mind that besides the projected Volume 7 on compilers, there were (are?) meant to be Volume 4, on Combinatorial Algorithms (which, judging by the handful of references to NP-Completeness in Volumes 1 - 3, was where complexity theory would be discussed), and Volume 5, on Lexical Scanning and Parsing (see the outline on pages vii-viii of the Preface to Volume 1). Perhaps the claim would be correct if the remaining volumes were published, but since this hasn't happened yet ....