Forgot your password?
typodupeerror
Image

Book Review: The Art of Computer Programming. Volume 4A: Combinatorial Algorithm 176

Posted by samzenpus
from the read-all-about-it dept.
asgard4 writes "Decades in the making, Donald Knuth presents the latest few chapters in his by now classic book series The Art of Computer Programming. The computer science pioneer's latest book on combinatorial algorithms is just the first in an as-of-yet unknown number of parts to follow. While these yet-to-be-released parts will discuss other combinatorial algorithms, such as graph and network algorithms, the focus of this book titled Volume 4A Combinatorial Algorithms Part 1 is solely on combinatorial search and pattern generation algorithms. Much like the other books in the series, this latest piece is undoubtedly an instant classic, not to be missing in any serious computer science library or book collection." Keep reading for the rest of asgard4's review.
The Art of Computer Programming. Volume 4A: Combinatorial Algorithms Part 1
author Donald E. Knuth
pages 883
publisher Addison-Wesley Publishing
rating 9/10
reviewer asgard4
ISBN 0-201-03804-8
summary Knuth's latest masterpiece. Almost all there is to know about combinatorial search algorithms.
The book is organized into four major parts, an introduction, a chapter on Boolean algebra, a chapter on algorithms to generate all possibilities (the main focus of the book), and finally 300 pages of answers to the many exercises at the end of every section in the book. These exercises and answers make this work an excellent companion for teachers of a university course.

The book begins with some introductory examples of combinatorial searching and then gives various definitions of graphs and directed acyclic graphs (DAGs) since a lot of combinatorial algorithms conveniently use graphs as the data structures they operate on. Knuth's writing style is terse and to the point, especially when he presents definitions and proofs. However, the text is sprinkled with toy problems and puzzles that keep it interesting.

After the introduction, the first chapter of the book (out of only two) is titled "Zeros and Ones" and discusses Boolean algebra. Most readers that have studied computer science in some form should be intimately familiar with most of the discussed basics, such as disjunctive normal forms and Boolean functions and their evaluation. The reader might be surprised to find a discussion of such an elemental foundation of computer science in a book on combinatorial algorithms. The reason is that storage efficiency is especially important for these types of algorithms and understanding the basic storage unit of computer systems nowadays (as the decimal computer is a definite thing of the past) is of importance.

After covering the basics of Boolean algebra and Boolean functions in quite some detail, Knuth gets to the most fun part of this chapter in my opinion: the section on bitwise tricks and techniques on integer numbers. Being a software engineer in the video games industry, I recognized a lot of the techniques from my day-to-day work, such as bit packing of data and various bit shifting and bit masking tricks. There is also a discussion of some interesting rasterization-like algorithms, such as the shrinking of bitmaps using Levialdi's transformation or filling of regions bounded by simple curves. The chapter concludes with Binary Decision Diagrams that represent an important family of data structures for representing and manipulating Boolean functions. This topic was also quite interesting to me since I have never been exposed to it before.

The second and main chapter of the book is titled "Generating All Possibilities". In this particular volume of the The Art of Computer Programming series, the only subsection of the chapter in this volume is on generating basic combinatorial patterns, or more specifically generating all n-tuples, permutations, combinations, partitions, and trees. We can expect more on this topic from Knuth in his continuation in Volume 4B and beyond.

The discussion on n-tuples starts out with a lengthy focus on Gray codes, which are binary strings of n bits arranged in an order such that only one bit changes from string to string.

A quite fun example for generating all permutations presented in this part of the book is alphametics, also sometimes known as verbal arithmetic — a kind of puzzle where every letter of a word stands for a digit and words are used in equations. The goal is to assign digits to letters in such a way that the equation is correct. A classic example is SEND + MORE = MONEY (the solution is left as an exercise for the reader).

The next section deals with generating all combinations. Given a set of n elements, the number of all possible combinations of distinct subsets containing k elements is the well-known binomial coefficient, typically read as "n choose k". One of the more interesting algorithms in this section of the book to me was generating all feasible ways to fill a rucksack, which can come in quite handy when going camping.

After combinations, Knuth moves on to briefly discuss integer partitions. Integer partitions are ways to split positive integer numbers into sums of positive integers, disregarding order. So, for example 3, 2+1, and 1+1+1 are the three possible partitions of the integer 3. Knuth, in particular, focuses on generating all possible integer partitions and determining how many there are for a given number. The book continues with a concise presentation of the somewhat related topic of set partitions, which refer to ways of subdividing a set of elements into disjoint subsets. Mathematically, a set partition defines an equivalence relation and the disjoint subsets are called equivalence classes; concepts that should be familiar to any mathematics major. Again, the focus is on generating all possible set partitions and determining how many partitions can be generated.

The main part of the book closes with a discussion of how to exhaustively generate all possible trees, which is a topic that I have never given much thought to. I am familiar with generating permutations, combinations, and partitions, but have never really been confronted with generating all possible trees that follow a certain pattern. One main example used throughout this part of the book is generating all possible strings of nested parentheses of a certain length. Such strings can be represented equivalently as binary trees.

Knuth's latest book is comprehensive and almost all encompassing in its scope. It compiles an incredible amount of computer science knowledge on combinatorial searching from past decades into a single volume. As such, it is an important addition to any computer science library. This book is not necessarily an easy read and requires a dedicated reader with the intention of working through it from front to back and a considerable amount of time to fully digest. However, for those with patience, this book contains a lot of interesting puzzles, brain teasers, and almost everything there is to know on generating combinatorial patterns.

On a final note, if you don't have volumes 1-3 yet you can get all volumes in a convenient box set .

Martin Ecker has been involved in real-time graphics programming for more than 10 years and works as a professional video game developer for High Moon Studios http://www.highmoonstudios.com/ in sunny California.

You can purchase The Art of Computer Programming. Volume 4A: Combinatorial Algorithms Part 1 from amazon.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.

*

This discussion has been archived. No new comments can be posted.

Book Review: The Art of Computer Programming. Volume 4A: Combinatorial Algorithm

Comments Filter:
  • by Anonymous Coward on Wednesday March 30, 2011 @03:30PM (#35670096)

    I already have the entire O'Reilly library, plus selected volumes from the "for dummies" and "...in 21 days" series. Why do we need another lousy computer book? This one doesn't even appear to cover anything useful like HTML coding or Adobe software.

    • Algorithms! We don't need no stinkin' algorithms!

    • by Dogtanian (588974)

      I already have the entire O'Reilly library, plus selected volumes from the "for dummies" and "...in 21 days" series. Why do we need another lousy computer book? This one doesn't even appear to cover anything useful like HTML coding or Adobe software.

      There's a Donald Knuth book for you too [knking.com]!

  • Yeah, but is it in 3-D? All the latest cool tech involves 3-D (soon to be the bell bottoms of this era).
  • 9/10 ??? (Score:5, Insightful)

    by condition-label-red (657497) on Wednesday March 30, 2011 @03:31PM (#35670106) Homepage
    After all the Foo for Dummies books that review on /. and rate a 10/10, Donald Knuth just gets a 9/10? Sad...
    • I think Knuth would agree that no work is ever perfect, and be satisfied with 9/10.

      I once had a grad school prof who would never give perfect marks on assignments (we had weekly assignments in addition to papers and other work), for the same reason. He would even takes 1/4 marks off (out of 10) for spelling and typographical errors.

      I once received an assignment back, marked 9-3/4 / 10. I hurried through the paper to find the error. Apparently there was a ribbon defect in the ribbon I used to print the fina

      • I'm betting you either loved that prof or absolutely hated him. Hopefully the former!
      • Was the prof Edward Tufte?
      • In a computer course? You betcha! If you're lucky, the compiler will find spelling errors and typos for you, and if you're not, it'll let them through to become runtime errors. When I was in college, we used the Cornell version of the PL/I compiler that auto-corrected mistakes, sometimes even correctly. (Since we were using punchcards, even having it correct them badly was helpful, because it would let more of your program run so you usually find one or two more bugs if you had any.)

      • I think Knuth would agree that no work is ever perfect

        Which doesn't harm it in the slightest. Bench pressing a barbell will give you the desired effect irrespective of whether you're a half centimetre off at extension. (The metaphor holds -- reading Knuth is weight training for the mind.)

        And SEND+MORE=MONEY isn't quite right, it's off by one. SEND+MORE=MONEY-A would work.

        • (removes a small disk from each ear) I should have written "+A". (sigh) I should never have signed that...

          What I did was to assign a simple sequence of A=1,B=2...Z=26 and sum the indices.

          I *want* that book...

    • The sad part is that quite possibly the only reason the book was given a 9/10 is because it is Knuth's book. Otherwise, as any other book on combinatorial algorithms, the book would never be reviewed, as the author doesn't have the faintest grasp on the subject, and this book review would be again dedicated to vacuous "learn X in n hours" books.

    • by raddan (519638) *
      People who review Foo for Dummies tend not to read books on theoretical computer science. The self-selection biases the scores, because their scoring criteria are different.
  • by perpenso (1613749) on Wednesday March 30, 2011 @03:36PM (#35670152)

    Much like the other books in the series, this latest piece is undoubtedly an instant classic, not to be missing in any serious computer science library or book collection.

    During a job interview I was given a test. Some questions/problems were good, other were not. One of the not-so-good questions presented 8 or so sorting algorithms and asked for their run time complexity (O notation). I answered bubble sort and quick sort and then added that I bought Knuth vol 3 so I didn't have to memorize such trivia. I'm not sure the engineer who created and graded the test liked the answer but the manager of the team (not an engineer) loved the answer after I explained what Knuth vol 3 was. I got hired.

    • by falzer (224563) on Wednesday March 30, 2011 @03:58PM (#35670414)

      I just tell potential employers that I ascended Nethack multiple times.

    • by hugetoon (766694)

      Don't look down on those questions. The day You try You will realize that designing good problems is *much* harder than solving them.

      • Don't look down on those questions. The day You try You will realize that designing good problems is *much* harder than solving them.

        That all depends on how the questions were presented. Was it a fill in the blank style question which really is trivia, or did it ask the participant to analyze actual code and determine the complexity himself? My hunch tells me it was a memorization type question, in which case his answer was pretty clever.

        • by mikael (484)

          Many companies (in the UK at least) have online pre-screening tests for candidates for C++ questions which are fairly easy to answer.

          Some are a bit strange like, "What is the least number of parenthesis you can leave this equation with, and still have it function as intended?" Something like: result = ( ( a && b ) & (c || (d | e ) ^ f ) );

          Presumably it's an optimization test, but really, I wouldn't want to change any piece of code unless there was something wrong with it in the first pl

          • by epee1221 (873140)

            Presumably it's an optimization test

            I dunno, it looks to me like this test is about memorizing operator precedence >_>
            Barring issues not mentioned in the problem statement, I'm rather inclined to let the compiler handle optimization on this.

            • by mikael (484)

              I'd agree with that - operator precedence vs. parenthesis writing. In the past, the recommended practise was to put separate operations in parenthesis in case of dodgy compilers that didn't handle precedence correctly, and also to mimc mathematical notation.

      • by perpenso (1613749)

        Don't look down on those questions. The day You try You will realize that designing good problems is *much* harder than solving them.

        Actually when I took that test I had already designed programming tests for job interviews at my previous employer. One of my first tasks at the new employer was to create a new test. I realize creating such tests is hard. The problem with the one I took was that the author had not really put much effort into it. It looked liked someone copied questions from undergraduate computer science quizzes.

      • by tixxit (1107127)

        That's true, but I think the question is bad on principle. I think a better question would be to give the interviewee a problem, and ask them what algorithm they'd use to solve it and why. For instance, what sorting algorithm (or data structure) would you use in the following situations, and why?

        1. Handle online sorting of packets that are usually in-order already, but occasionally not?
        2. Sort a terrabyte of data?
        3. Sort a list of ~1000 items in memory?

        This is better because it doesn't require the person to rememb

        • smoothsort, mergesort, quicksort. where's my job?
        • Nah, the real question to ask is whether bogosort or bozosort is less efficient... That shows the true wizard.
        • by owlstead (636356)

          The answer to the third option is easy: anysort (tm). Sometimes you just don't care (unless you have to do many in a loop). Quicksort is probably the workhorse to use, but I would rely on the platform.

          One rather interesting fact: you got those exercises at university where you had to calculate which sorting algo was more efficient given a number of elements. Of course, easier algo's may be more efficient if the set is small. But the simple fact is that most of the time, small sets are not interesting anyway

    • Did the position give you the opportunity to apply that knowledge?
      • by perpenso (1613749)

        Did the position give you the opportunity to apply that knowledge?

        Yes. I needed to sort data in a time critical manner. I thought about the nature of my data, mostly already sorted, consulted Knuth's summary table and tried the algorithm he identified as having good performance on data of that nature. After implementation I profiled a run with a large data set and the sorting code barely showed up, 1% execution time. Good enough, moved on to next task.

    • Excellent section on sorting. I sped up a sort program 100x using that, after much study and fine tuning. This was back in the late 70s on an 8 bit machine with 8k of RAM to play with. Several years later, we switched hardware and interviewed some clown, who, when asked what he would do, said he would allocate a 1MB array and use bubble sort. Ouch!

      • I remember when I first got to use Virtual Machines, on an IBM VM/CMS system back in the mid-late 70s. You could define a virtual machine with a whole megabyte of storage! That was as big as a quarter of the physical RAM on the whole mainframe, not that it would actually all be in core at once!

        And yeah, Knuth's volume on searching and sorting was really important when computers had that kind of scale, and the principles mostly still apply even now when disk drives are the slow part and tapes don't exis

        • by Mr Z (6791)

          The sorting stuff came in handy for me when doing incredibly small sorts, ironically enough. Median filters end up being small sorts. With a 5x5 or 7x7 median filter, you've got 25 or 49 pixels and need to find the median pixel value quickly. Interestingly enough, I ended up using a combination of sorting networks and insertion sort a partially sorted pixel buffers for 7x7. (Partially sorted because the 7x7 kernel for adjacent pixels overlaps and so you can take advantage of the partial sorting in the o

    • Seriously... D-Bags who think a good engineer is someone who has memorized weird minutia should not be making decisions on hiring... and neither should HR.

      -Do you have experience with software development? (a good developer can learn any language and use the correct constructs)
      -Can I see code examples? (Proof of code quality)

      -Please return for interview two... [call 24 hours before and ask for code for a simple program in their preferred language to be brought with them] (validation of code quality)

      -You ar

    • by chgros (690878)

      How is calculating complexity "trivia"? Were the algorithms only described by name?

      • by perpenso (1613749)

        How is calculating complexity "trivia"? Were the algorithms only described by name?

        There was no calculation of complexity. There was merely the regurgitation of the textbook run time complexity of XXXsort that assumed randomly ordered data, ignored constants, assumed a sufficiently large n, etc. It was literally something like: Q. Bubble sort? A. O(n^2).

    • by t2t10 (1909766)

      You shouldn't have to memorize that stuff, you should be able to figure it out.

  • by Anonymous Coward on Wednesday March 30, 2011 @03:36PM (#35670154)

    Someone actual read The Art of Computer Programming? Are you sure it wasn't just sitting on your shelf?

    • by fishbowl (7759)

      I often found the whole focus on the MIX hypothetical machine to be counterproductive to learning the material. I always went to CLR first for anything, and to Knuth for certain things where I wanted more depth or just a different explanation. Knuth's pseudocode resonates with me fairly well, but MIX examples tended to just give me headaches. Yes, I did read the introduction, and yes I'm glad he didn't try to use any of the languages that were in vogue in 62.

      • Languages in vogue in 62? (Not that the first volume actually shipped until 68...)

        • That would be Algol, which would have been a great language for Knuth to teach in (and the CACM used it for most articles about algorithms for years, though they still tended to be in Fortran then.)
        • LISP was around, but was sufficiently abstract that it wouldn't have matched most of the things Knuth was trying to teach because it doesn't have the physicality.
        • But even F0RTRAN II would have been better than Knuth's pseudo
      • by martyros (588782)
        Yeah -- I bought the first three as a set, but I never could bring myself to invest the effort to learn an imaginary language. The book could have been written in a very simplified C, which can be trivially reduced to assembly if need-be, but can be easily read by nearly any programmer today. His books could have a much wider impact if they were translated into something that had a lower barrier-to-entry.
    • In the movie Real Genius, when Jordan is guarding the hallway filled with ice, she's holding a volume of Knuth. Upside down. Sure, a bit of light reading.

      So no, it's not just for sitting on the shelf. :-)

    • What? It has words inside??
  • by Millennium (2451) on Wednesday March 30, 2011 @03:38PM (#35670178) Homepage

    Knuth's books are awesome, not just for the content (which would itself be a bargain at quadruple the price) but also for the sheer intimidation factor.

    However, I've got to admit: the volumes I'm most looking forward to -5, 6, and 7- are yet to come. This bothers me, because with the way Volume 4 keeps growing, I'm no longer convinced that he's going to live long enough to finish the series, not because of any slowness on his part but because the work just keeps getting bigger and bigger. Has he made arrangements for others to finish the series in case the worst happens?

    • not because of any slowness on his part

      He banged out volumes 1, 2 and 3 over about 5 years. It's been nearly 40 years since then with relatively little progress. Something has slowed knuth down big time whether it is other commitments, reduction in mental capacity, inceasing complexity of the work or some combination thereof.

      • by larry bagina (561269) on Wednesday March 30, 2011 @04:07PM (#35670526) Journal
        That something was TeX. Have you ever tried using it? We're lucky he got part A out. The entire chapter (not just part A) would have been published 30 years ago if he hadn't been dicking around with the font, margins, gutters, line breaks, etc.
        • by raddan (519638) *
          I know you're kidding, but TeX is a seriously great piece of software. LaTeX would not be possible without TeX, which is the de facto standard for typesetting mathematical and scientific papers. And it's easy to use. Have you ever tried using Word or OOo to write anything substantive about math? Forget about it. Learning LaTeX is one of the first items on the agenda of a new grad student in my department. So I tend not to think of TeX as a waste of time on Knuth's part.
          • by mikael (484)

            Oh yes, I wrote my MSc thesis in Latex and PhD in Word.

            The biggest problem with Word was that page numbering was a pain, because the front pages have no numbering, everything from the introduction, table of contents, list of figures is page numbered in roman numerals. The rest of the chapters are numbered normally. You also need a list of special keywords which are all in italics, not forgetting that the plurals of some words are hyphenated, while the singular isn't.

            With mathematical equations, matrices are

        • by syousef (465911)

          That something was TeX. Have you ever tried using it? We're lucky he got part A out. The entire chapter (not just part A) would have been published 30 years ago if he hadn't been dicking around with the font, margins, gutters, line breaks, etc.

          Leave the poor man alone. He's just trying to build an alternative to MS Word that isn't O(n^2) ;-)

      • There was this little thing called TeX that occupied a bit of his time....

        Last time I saw Knuth, he was over at Techshop making stuff on the laser cutter.

    • by assantisz (881107)
      Well, according to his own website (http://www-cs-faculty.stanford.edu/~knuth/taocp.html) his plan is to finish volume 5 by 2020 and will then revisit volumes 1-3 to update them. And only then, and if he's still alive, will ge start on volumes 6 and 7, which he doesn't count as "central core of computer programming for sequential machines", though.
      • by vlm (69642)

        Well, according to his own website (http://www-cs-faculty.stanford.edu/~knuth/taocp.html) his plan is to finish volume 5 by 2020 and will then revisit volumes 1-3 to update them. And only then, and if he's still alive, will ge start on volumes 6 and 7, which he doesn't count as "central core of computer programming for sequential machines", though.

        In his latest book collected papers on fun and games he referred to it as his last book. Hopefully his last book as in last book of the "collected papers" series.

  • Decades in the making, and all he can complete is Volume 4A part 1. How long for part 2? Will we ever see 4B?

  • Fun stuff. I guess I'll need to buy the book. If you know the theory behind things, you can often do a better job of making things work.
  • I spend all day writing Model-View-Controller, DAOs, debugging, and writing JavaScript. Reading rich algorithmic stuff really just makes me sad.
    • by JoeD (12073)

      Your comment makes me sad. You're missing so much really beautiful stuff that will help you in ways that you can't even imagine, and you don't even know it.

      • Like I said above, the people selling to the client understand little, so nothing complex is sold to them. Besides, you can't really use an algorithm your boss doesn't understand, can you? Knuth is the enticement into the world of programming, but the reality is usually grinding out crap for businesses.
        • by idontgno (624372)

          Good point.

          The pipefitter may admire and envy the sculptor, but the pipefitter that tries arranging the plumbing into something like a Highfield [annawilihighfield.com] is the pipefitter that loses his job and his union card.

          Still, I don't think you should just walk away from Knuth, even if it doesn't pay the bills. Some parts of Knuth are art. Some parts of Knuth are more like craft. Some parts of Knuth is just basic workmanship. I recommend reading it for your own edification, just like the pipefitter may want to be an amateur s

        • by raddan (519638) *
          Sure, but if you ever find yourself in the position of needing to scale things up quickly, you'll be glad you have a little theory in your corner. You'll know which parts of your program you can trivially parallelize, how to keep things moving quickly with hardware constraints, and how to save yourself work by using the more powerful features of your language. Programming is a blend of science and art, and your work will be a lot more fulfilling if you see it that way. This is coming from someone who chu
  • by jmcbain (1233044) on Wednesday March 30, 2011 @03:48PM (#35670312)

    This new book combines all of the previously-published Volume 4 fascicles from 2005 to 2009, all of which I bought last year and am still reading. Those fascicles are:

    • Volume 4 Fascicle 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)
    • Volume 4 Fascicle 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)
    • Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005)
    • Volume 4 Fascicle 3, Generating All Combinations and Partitions (2005)
    • Volume 4 Fascicle 4, Generating All Trees; History of Combinatorial Generation (2006)

    All the volumes combined are a true masterpiece for the computer science community. I do not know of many other fields in the sciences where the core ideas, both theoretical and practical, are wrapped up so well. The only comparison I know of is The Merck Manual for physicians. If anyone knows of definitive and comprehensive readings for other engineering fields like EE, CivilE, or ChemE, I'd like to know of them.

    • by vlm (69642)

      If anyone knows of definitive and comprehensive readings for other engineering fields like EE, CivilE, or ChemE, I'd like to know of them.

      Closest I've got for EE is either the classic "Art of Electronics" or an ARRL handbook...

      • by fwice (841569)

        Closest I've got for EE is either the classic "Art of Electronics" or an ARRL handbook...

        Completely agree on "The Art of Electronics". I'm curious what other people mention. My go-to books as an ECE are TAOCP, TAOE, and "Introduction to Algorithms" by Rivest et. al.

        On the second tier are "The Practice of Programming" by Kernighan & Pike, "Hacker's Delight" by Warren, "The Pragmatic Programmer" by Hunt & Thomas, and a bunch of even more specific books on DSP, Stoch, and C. But these are a bit more subject specific and 'opinion' then reference a la the first tier.

    • by Rostin (691447)
      For chemical engineering: Perry's Chemical Engineers' Handbook.
    • by metlin (258108)

      For a while, Resnick & Halliday was the mecca for Physics, and Morrison & Boyd for Organic Chem. Can't really speak to other areas.

    • "Molecular Biology of the Cell" (colloquially: The Cell), is kind of like TAoP for cell biology. It's not short though. But combining all the TAoP Volume 4 Fascicles together, you are already at a large fraction of the amount of pages in The Cell. So I guess it's what you are looking for.

    • If you don't understand the combinatorial stuff, how do you follow calculating the order of a sort?

    • I didn't get the fascicles 'cuz I figured they'd melt if I took them out of the freezer.
    • by moller (82888)

      When I was in undergrad everyone referred to Calculus - Vol I and II by Tom M. Apostol as the mathematician's bible.

  • Now my 3 volume slipcased set will look awkward and incomplete and knaw away at me every time I see additional books next to it that I know conceptually belong in the slipcase.
    • by Imagix (695350)
      You could just buy the 4-book slipcase... it even comes with a bonus copy of volumes 1-4 that you can give to someone else! :)
  • SEND + MORE = MONEY
    0001 + 0001 = 00010

    The Art Of Cheating, Problem?

  • by lee1 (219161) <`lee' `at' `lee-phillips.org'> on Wednesday March 30, 2011 @05:09PM (#35671232) Homepage
    A stunning result [plos.org] probably too recent to have made it in to the book under review: we now have a closed-form formula for the partition numbers.
  • Knuth on the Bible (Score:4, Interesting)

    by benjto (1175995) on Wednesday March 30, 2011 @06:13PM (#35671922)

    I respect Knuth for his stand that a man of such technical sophistication does not have to be at odds with faith. In fact, he wrote a pictorial Bible study:

    http://www.amazon.com/3-16-Bible-Texts-Illuminated/dp/0895792524

    Knuth as quoted from a reviewer:

    "it's tragic that scientific advances have caused many people to imagine that they know it all, and that God is irrelevant or nonexistent. The fact is that everything we learn reveals more things that we do not understand... Reverence for God comes naturally if we are honest about how little we know."

    • Re: (Score:3, Insightful)

      by ChrisMaple (607946)
      Reverence for "God" comes from an abject failure in critical thinking on that subject.
  • The computer science pioneer's latest book on combinatorial algorithms is just the first in an as-of-yet unknown number of parts to follow.

    The dude is 73 years old. There's a good chance we won't see any more volumes from him considering how long this one took. There was a fair amount of doubt that 4a would ever see print.

    Now if we can just get those hyperlongevity + brain mapping technologies working...

  • 28 years (Score:5, Interesting)

    by EdwinFreed (1084059) on Wednesday March 30, 2011 @11:23PM (#35674450)

    Back in 1983, when I was still in school, I published an article in Dr. Dobb's Journal on how to perform various binary operations efficiently. I also sent a letter to. Knuth describing one algorithm in particular: An efficient means of calculating a weighted sum of the bits in a word.

    The minute I put the letter in the mailbox I regretted bothering Knuth with such a trivial matter. I was greatly relieved when there was no response; I assumed the letter had circular-filed.

    Then about three years ago I got a phone call from someone working with Knuth. They informed me that after 25 years my letter was about to become an exercise in volume 4A, and asking how I wanted my name to appear in the index. And now the book is out, and there it is: Section 7.1.3, exercise 44.

    It goes without saying that I was delighted by what happened. But even more than that, I am in awe of the level of scholarship behind this work, where such a little thing as this algorithm was tracked for almost three decades.

  • Where's the eBook. As a matter of principal (and the fact that I don't want to buy a bigger house) I have stored away all my computer books which are available in eBook form whether I've purchased the eBook or not as I can more easily buy it then find the printed copy on my old shelves. I am looking forward to moving all my printed books to the recycling bin in the future. This is 2011, there's just no reason for printed books anymore... well except for going to the book store to find things which look inte

"Out of register space (ugh)" -- vi

Working...