Become a fan of Slashdot on Facebook

 



Forgot your password?
typodupeerror
×
Programming Announcements Technology

Knuth's Art of Computer Programming Vol. 4 289

_mutators writes "bookpool.com has posted an excerpt from Knuth's long awaited The Art of Computer Programming: Volume 4. It is very short and discusses combinatorial searching. But when will it be published? Bookpool does not hazard a guess."
This discussion has been archived. No new comments can be posted.

Knuth's Art of Computer Programming Vol. 4

Comments Filter:
  • by HyperChicken ( 794660 ) on Thursday February 03, 2005 @10:21PM (#11569252)
    The books homepage, http://www-cs-faculty.stanford.edu/~knuth/taocp.ht ml [stanford.edu] offers the fascicle for download for free. http://www-cs-faculty.stanford.edu/~knuth/fasc1.ps .gz [stanford.edu] You can still get $2.56 for each bug found, I believe.

    Mirrors:
    http://www-cs-faculty.stanford.edu.nyud.net:8090/~ knuth/taocp.html [nyud.net]
    http://www-cs-faculty.stanford.edu.nyud.net:8090/~ knuth/fasc1.ps.gz [nyud.net]
  • /.ed (Score:3, Funny)

    by mrwoody ( 856093 ) on Thursday February 03, 2005 @10:23PM (#11569266)
    The next volume will be:
    "The Art of Being Slashdotted"
  • It's been a while. (Score:5, Informative)

    by robbyjo ( 315601 ) on Thursday February 03, 2005 @10:23PM (#11569268) Homepage

    It's been a while. Dr. Knuth already finished pre-fascicle 4. Get it here [stanford.edu]. It's far from done (well, according to his plan [stanford.edu]).

  • Nifty from the Knuth (Score:3, Informative)

    by gateman9 ( 733995 ) on Thursday February 03, 2005 @10:24PM (#11569274) Homepage Journal
    Nifty, but mainly from the whole CS angle. And it seems a bit more approachable that the third book was, although some of that has to do with the fact that I was relatively unschooled when I first read them.

    It'll be a pleasure to add it to my bookshelf.
  • Many own, few read (Score:5, Insightful)

    by Ars-Fartsica ( 166957 ) on Thursday February 03, 2005 @10:27PM (#11569284)
    How many people have bought the entire Knuth series just to occupy the moral high ground on their bookshelf? For my money, Cormen/Leiserson/Rivest's "Introduction to Algorithms" is preferred for almost all related material you might want to investigate.
    • TAOCP Volume 1, First Edition, 1968
      TAOCP Volume 2, First Edition, 1969
      TAOCP Volume 3, First Edition, 1973

      Introduction to Algorithms, First Edition, 1990

      Notice the slight gap in publication dates?

      • by fm6 ( 162816 ) on Thursday February 03, 2005 @11:21PM (#11569493) Homepage Journal
        I seem to recall reading that TAOCP was originally intended as a single volume. The project grew, because computer science grew as fast as Knuth could write. In the late 70s, Knuth joked that people should please stop doing any research, so he could finish the series!

        I used to assume that Knuth simply acknowledged that CS had gotten too big to be summarized by a single introductory text. But it turns out that he's still working on it, even as the size of the project continues to grow. ("Volume 4" will actually be 4 volumes [stanford.edu]!) There's some weird obsession here, possibly characterized by Knuth's abandonment of email [stanford.edu] and certainly connected with his early retirement [stanford.edu].

        It's also strange that Knuth still insists providing code for a pseudo machine [stanford.edu]. I'm a CS flunkout, so my opinion isn't worth much, but this does seem to be a thoroughly obsolete idea. Especially when you consider how many effort Knuth expends redesigning the machine!

        • by Anonymous Coward on Thursday February 03, 2005 @11:27PM (#11569511)
          Using MIX/MMIX is brilliant.

          First, it stops copy-and-pasters. You have to actually read the books to gain knowledge.

          Second, it shows the algorithms on a low level. Very good.

          Third, as he's said, he doesn't have to update his book when the "language of the decade" changes.
          • by fm6 ( 162816 )

            First, it stops copy-and-pasters. You have to actually read the books to gain knowledge.

            How does it stop c&p? Nobody studies Knuth without a MIX or MMIX emulator at hand.

            Besides, if you're stupid enough to study CS without actually reading the code, you have no hope of even BSing your way through a course.

            Second, it shows the algorithms on a low level. Very good.

            Good that you spend all your effort twidling bits, instead of understanding the algorithm?

            Third, as he's said, he doesn't have to upd

            • So instead he has to update it for the machine architecture of the decade.

              • MIX: ~1964.
              • MMIX: 1999.

              I think he's doing a bit better than "decade."

              As he says, part of the reason for MMIX is that many of the concepts needed for a good machine of this type had not been discovered when MIX was around. Now that things are to a state where they can be well-expressed, he's using a new model. Well, that and we tend to use floating point and ASCII these days.

              • by fm6 ( 162816 )
                There was a version in between called MIXMaster.

                Your other comments rest on the assumption that you can only talk about algorithms by writing code in an actual executable language. But lots of CS books don't do that. They rely on pseudo-code, or they compare implementations in various high- and low-level languages. Even TAOCP is written so you can skip over the MIX parts.

                Besides, if the code examples are obsolete in 10 years, so what? Most textbooks require major revision after that long. (Not to be con

                • The more I think about it, the more I'm convinced that Knuth had what seemed like a good idea 40 years ago and can't let it go. (Actually, two of them; the other was that he could write a single comprehensive CS textbook.)

                  If his idea is to write a comprehensive CS textbook, then that probably is a mistake. Whatever comes out of the process certainly is interesting, however.

                  Your other comments rest on the assumption that you can only talk about algorithms by writing code in an actual executable languag

            • Nobody studies Knuth without a MIX or MMIX emulator at hand.

              I thought you were supposed to write your own emulator. After all, he does give instructions on page 100 or thereabouts.
        • by Alomex ( 148003 ) on Thursday February 03, 2005 @11:37PM (#11569545) Homepage
          Knuth is stubborn. That is his best and his worst attribute. He should have given up on MIX and on writing volume 4 on his own a long time ago. On the other hand if he weren't that stubborn, he would have never produced the first two volumes or the TeX formatting engine.

        • by Anonymous Coward
          A pseudo machine is actually a very good idea. It lets you present the ideas that you want to present in a fashion that is clear-cut and precise, without relying upon a given platform being available however many years down the track.

          Case in point: the first volume of TAOCP was published in the late 1960s. How many systems that were available in the 1960s are still available? None. Even IBM's mainframes have undergone architectural changes between then and now, although they do (or at least should; I don'

          • One of the tricks of MIX was that it could be a binary computer or a decimal computer. You never knew which it was at any one time so it challenged some assumptions. Too bad the MMIX is a binary beast.
        • by Zeinfeld ( 263942 )
          I used to assume that Knuth simply acknowledged that CS had gotten too big to be summarized by a single introductory text. But it turns out that he's still working on it, even as the size of the project continues to grow. ("Volume 4" will actually be 4 volumes!)

          I first met Knuth before I started my doctorate, that was almost twenty years ago. Volume 4 was already notoriously overdue at the time.

          I don't think that Knuth's objective is suited to a book any more. The most appropriate form for an encyclopea

      • Isn't that because he got frustrated with the state of typography in his books, so did the proper hacker thing and spent a decade or so writing TeX?
    • by nomadic ( 141991 ) <nomadicworld@ g m a i l . com> on Thursday February 03, 2005 @10:49PM (#11569388) Homepage
      How many people have bought the entire Knuth series just to occupy the moral high ground on their bookshelf?

      That's absolute nonsense. I often will take one of his volumes off the bookshelf, put La Boheme on the stereo (the Pappano recording, of course) , pour myself a glass of Le Montrachet '78, and peruse Prof. Bluth's delightful words. You shouldn't be bitter just because you're too uncouth to understand them.
      • Don't forget to run all example code with the '79 MIX machine - it just wouldn't do to use something as lowbrow as (gasp) an emulator to run Dr. Knuth's heavenly code. It has to be a '79, of course - I swear, they stopped making real computers after '79. They just don't make 'em like they used to.

        And afterwards, a relaxing steam bath powered by the Pentium-4 watercooling kit, and a organic avocado facial to let the pure ephemeral brilliance of Dr. Knuth's equasions sink in.
      • God. How....Proustian. *swirls brandy*
      • His description of the elegance of balanced-ternary as a compact method of representing numbers is a joy to read.

        But I personally find MIX assembly language virtually impenetrable. The instruction mnemonics seem to be designed to impede understanding, not assist it, and the damn thing doesn't even have a "return from subroutine" instruction - you have to self-modify a jump! Recursive algorithms become instantly nasty.

        I am glad he's changing this to a more modern, RISC-like architecture, which is likely to
    • by cecom ( 698048 ) on Thursday February 03, 2005 @10:51PM (#11569391) Journal

      While I was growing up in Eastern Europe, it was completely impossible to find any of the volumes. They weren't available for sale and almost all copies had been stolen from the libraries (well, not exactly "stolen" but many people forgot to return the book and would much prefer to pay the library fine).

      I eventually managed to get a hold of "Searching and Sorting" for a couple of days and I tried to read it. Needless to say, I didn't get far. One needs months to consume the whole thiing :-)

      When I moved to the US, the first thing I did was to buy the series. I couldn't believe that it was actually available in stores! I have to admit though, I still haven't read the three volumes completely - ah, I miss the enthusiasm of my youth.

      Didn't somebody say that one should never attempt to read the whole thing ? One should turn to a specific section and read it only when the need arises. That makes me feel better :-)

    • There are at least a couple of important subjects where the use of MIX in AoCP makes a subject more immediately accessible than Intro Algorithms.

      I do agree that there are probably quite a few copies of AoCP occupying bookshelves for no reason other than to impress visitors.

    • I've got both the first and second edition of Cormen/Leiserson/Rivest. It's a great text.
    • And for the rest, its more of a convenience thing. The way it works is, you look in CLR (Cormen, Lieserson, Rivest). If you find useful leads from there, you go follow them, or go to google or citeseer or something.

      After a while, you get a little more curious (or a bit stuck with counting things down to the last epsilon), so you go look at Knuth. Finally, if nothing else works, you sit down and prove it.

      Personally, Knuth, Graham & Patashnik, and Hopcroft & Ullman have bailed me out more often th

    • Algorithms in C, volumes 1 through 5. Absolutely the best comp sci book out there. One page of Knuth makes me sleepy. Sedgewick reads like a good detective story - you can't put it down.
    • Hah! I got my volumes for free out of the damaged returns bin when I worked for Amazon. I mock you! I mock you all!

    • CLR is a very good, thorough, book. (The book weighs about 100 lbs). For example, I've been working with a lot of graph theory lately, and CLR had some good information about relaxed heaps, fibonacci heaps, and even pointers to Ahuja's "Faster algorithms for the shortest path problem."
    • by deunhido ( 646288 ) on Friday February 04, 2005 @02:38AM (#11570140)

      "It's a pleasure to meet you, Professor Knuth," Steve said. "I've read all of your books."

      "You're full of shit," Knuth responded.

      From folklore.org [folklore.org]

    • I have knuth 1-2-3, the only reason I found for needing "Introduction to Algorithms" is the description contained there-in for red-black trees (which is painfully missing in knuth).
    • How many people have bought the entire Knuth series just to occupy the moral high ground on their bookshelf? For my money, Cormen/Leiserson/Rivest's "Introduction to Algorithms" is preferred for almost all related material you might want to investigate.

      The Big White Book of Algorithms is a fine book. It is much more accessable than Knuth (Examples in assembly instead of pseudocode? Please! At that point Knuth is just telling his reader "I'm smarter than you." Yeah, no shit Mr. Theory of Computing. Th
  • Still Waiting (Score:5, Interesting)

    by Detritus ( 11846 ) on Thursday February 03, 2005 @10:29PM (#11569290) Homepage
    When I bought Volume 3, about 20 years ago, it included a postcard that the buyer could mail to the publisher, to be added to a mailing list for notification when Volume 4 was published. I sent in the postcard.

    I'm still waiting.

  • by RedWizzard ( 192002 ) on Thursday February 03, 2005 @10:30PM (#11569294)
    But when will it be published? Bookpool does not hazard a guess."
    Um, they said 2007. So what, do story submittors not bother to RTFA either these days?
  • Check the left column of http://www.bookpool.com/.x/SSSSSS_C473S597521D0502 011740/ct/163 [bookpool.com]. You can buy parts of Vol. 1 (revised) and 4 already, in addition to the one part that's ready for free download. They also say they expect to be able to sell you the entire volume 4 in 2007. And I'll bet Knuth doesn't slip nearly as bad as Longhorn.
  • 2007 (Score:3, Informative)

    by CEHT ( 164909 ) on Thursday February 03, 2005 @10:42PM (#11569344) Homepage
    Knuth made a suggestion that he would have vol 4 published in 2007. I wouldn't doubt his estimation if he wrote down a deadline for himself, and everyone else.
  • Dear Knuth (Score:5, Funny)

    by Letter ( 634816 ) on Thursday February 03, 2005 @10:44PM (#11569354)
    Dear Knuth,

    After Vol. 4 are you going to do some "prequels?" So 1-4 are actually, say, 3-6, and then the new Vols. 1 and 2 include new special effects capable only in LaTeX2e?

    Letter

  • by danny ( 2658 ) on Thursday February 03, 2005 @11:06PM (#11569452) Homepage
    You might be interested in my review of volumes 1 to 3 [dannyreviews.com].

    I'm off to ask Addison-Wesley for a review copy of volume 4!

    Danny.

  • Question (Score:4, Interesting)

    by Spy der Mann ( 805235 ) <spydermann.slash ... com minus distro> on Thursday February 03, 2005 @11:08PM (#11569462) Homepage Journal
    Is this the same Knuth that wrote along with Morris and Pratt the famous string matching algorithm [uci.edu]?
    • Yes, it's the same Knuth. But Boyer-Moore [utexas.edu] is almost always a better algorithm to use.
  • by iJames ( 846620 ) on Thursday February 03, 2005 @11:35PM (#11569536) Homepage
    Man. At this rate, he's never going to get to the Dark Tower.
  • There's a fun bit in (Score:5, Interesting)

    by multiplexo ( 27356 ) on Friday February 04, 2005 @12:37AM (#11569769) Journal
    The Atrocity Archives [amazon.com] by Charles Stross where one of the characters reveals that the reason why Knuth hasn't released volume 4 is that it contains a hack that allows you to solve non-deterministic polynomial (NP) problems in polynomial time. This is such a huge secret that the world's intelligence agencies, who already know how to do this, have an agreement with Professor Knuth where as long as he doesn't publish volume 4 they won't render him metabolically challenged (i.e, "dead".

    The Atrocity Archives is a way cool book, I heartily recommend it to /. geeks. Stross used to work as a programmer/sysadmin so it's a lot of fun if you've ever worked in IT.

  • For many years, I wondered which volume 4 would win the race; this one or Star Wars. Too bad the wrong one won!

  • by Admiral Burrito ( 11807 ) on Friday February 04, 2005 @04:21AM (#11570423)
  • I hear they're bundling Duke Nukem Forever with Knuth's ACP vol. 4. Might just be a rumor, though ...
  • Bookpool! (Score:3, Informative)

    by WPIDalamar ( 122110 ) on Friday February 04, 2005 @09:44AM (#11571736) Homepage
    I used to work for bookpool (4 or so months ago). They're a great group of people dedicated to serving the customer. Little known fact: They are on the Island of Martha's Vineyard off the coast of Massachusetts!

    Their prices are usually the best around, and they ship things out quick. So after the slashdotting, be sure to check them out for tech books.

    I'm curious... how many people had heard of them before today?

We are Microsoft. Unix is irrelevant. Openness is futile. Prepare to be assimilated.

Working...